/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    vector<vector<int>> result;
    void helper(TreeNode* root, int sum, vector<int>& vec) {
        if (root == nullptr) {
            return;
        }
        vec.push_back(root -> val);
        sum -= root -> val;
        if (root -> left == nullptr && root -> right == nullptr) {
            if (sum == 0) {
                result.push_back(vec);
            }
            else {
                vec.pop_back();
                sum += root -> val;
                return;
            }
        }
        if (root -> left != nullptr) {
            helper(root -> left, sum, vec);
        }
        if (root -> right != nullptr) {
            helper(root -> right, sum, vec);
        }
        vec.pop_back();
        sum -= root -> val;
    }
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<int> vec;
        helper(root, sum, vec);
        return result;
    }
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root||root==p||root==q)
            return root;
        TreeNode *left=lowestCommonAncestor(root->left,p,q);
        TreeNode *right=lowestCommonAncestor(root->right,p,q);
        if(left&&right)
            return root;
        if(!left)
            return right;
        if(!right)
            return left;
    }
};

3.是否是bst的后续便利

bool isbst(int a[],int length){
  if(a==null||length<=0)
    return false;
  int root=a[l-1];
  int i=0;
  for(;i<length;++i)
    if(a[i]>root)
      break;
  int j=i;
  for(;j<length;++j)
    if(a[j]<root)
      return false;  
  bool left=true;
  if(i>0)
    left=isbst(a,i);
  bool right=true;
  if(j>0)
    right=isbst(a+i,j-i-1);
  return left&&right;
}

4.二叉树转链表

class Solution {
public:
    TreeNode* prev=NULL;
    void flatten(TreeNode* root) {
        if(root==NULL)return;
        flatten(root->right);
        flatten(root->left);
        root->left=NULL;
        root->right=prev;
        prev=root;
    }
};

5.bst转双向链表

bstNode *convert(bstNode *root){
    bstNode *Last=nullptr;
    convertNode(root,&LastNode);
    bstNode *head=Last;
    while(head!=null&&head->left!=null)
        head=head->left;
    return head;
}
void cN(bst *node,bst** Last){
    if(node==null)
        return;
    bst *cur=node;
    if(cur->left!=null)
        cn(cur->left,last);
    cur->left=*last;
    if(last!=null)
        (last)->right=cur;
    *last=cur;
    if(cur->right!=null)
        last->right=cur;
    last=cur;
    if(cur->right!=null)
        cn(cur->right,last);
}

6.第k小的元素

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        return kthdfs(root, k);
    }
    int kthdfs(TreeNode *root,int &k){
        if(!root)
            return -1;
        int val=kthdfs(root->left,k);
        if(k==0)
            return val;
        if(--k==0)
            return root->val;
        return kthdfs(root->right,k);
    }
};

7.序列化
8.删除bst一个点