leetcode

• 剑指 Offer 33. 二叉搜索树的后序遍历序列
• • 题目
  • 代码
• 剑指 Offer 34. 二叉树中和为某一值的路径
• • 题目
  • 代码

主要的想法就是递归。

class Solution {
public:
    bool check(vector& postorder,int st,int en) {
       if(st >= en) {
           return true;
       }
        int root = postorder[en];
        //左子树节点的值小于根节点的值
        int i = st;
        for(i = st; i < en  ;i++) {
            if(postorder[i] > root) {
                break;
            }
        }
        //右子树节点的值大于根节点
        int j = i;
        for(; j < en; j++) {
            if(postorder[j] < root) {
                return false;
            }
        }
       
        //判断左子树是不是二叉搜索树
         bool left = check(postorder, st, i);
         //判断右子树是不是二叉搜索树
         bool right = check(postorder, i, en);
         return (left&&right);
    }
    bool verifyPostorder(vector& postorder) {
        //二叉搜索树，左子树小于父节点，小于右子树
         int sz = postorder.size();
         return check(postorder,0,sz - 1);
    }
};

class Solution {
public:
    vector> res;
    vector path;
    void dfs(TreeNode* root, int target) {
        if(root == nullptr) {
            return;
        }
        //减去当前node的值，并加入路径
        path.push_back(root->val);
        target = target - root->val;
        //到达叶子节点
        if(root->left == nullptr && root->right == nullptr && target == 0) {
            res.push_back(path);
        }
        dfs(root->left,target);
        dfs(root->right,target);
        //将本次搜索结果移除,向上回溯
        path.pop_back();

    }
     //查找目标和的所有路径，dfs
    vector> pathSum(TreeNode* root, int target) {
       dfs(root,target);
       return res;
    }
};