代码随想录day18

513.找树左下角的值

本题用前中后序都可以（都是先遍历左再遍历右，保证最后一定是左侧的节点），因为没有中节点的处理逻辑，用全局变量记录最大深度，只要遇到叶子结点并且当前深度比最大深度大，就更新，同时用到了回溯。

深度最大的叶子结点是最后一行。左侧的节点不一定是左孩子。

class Solution {
public:
    int maxDepth=0;
    int res;
    void traversal(TreeNode* node,int depth){
        if(node->left==NULL&&!node->right&&depth>maxDepth){
            maxDepth=depth;
            res=node->val;
        }
        if(node->left){
            depth++;
            traversal(node->left,depth);
            depth--;
        }
        if(node->right){
            depth++;
            traversal(node->right,depth);
            depth--;
        }
    }
    int findBottomLeftValue(TreeNode* root) {
        traversal(root,1);
        return res;
    }
};

迭代法：（层序遍历）

用每一层的第一个元素更新结果值res，最后返回的就是最后一层第一个元素。每次循环，队列都要一边弹出元素一边加入元素。

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        if(root) que.push(root);
        int res;
        while(!que.empty()){
            //先记录当前层的元素个数
            int size=que.size();
            for(int i=0;i<size;i++){
                TreeNode* node=que.front();
                que.pop();
                if(i==0) res=node->val;
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return res;
    }
};

112. 路径总和 

也是前中后序都可以，不存在中节点的处理逻辑。代码中有两处返回false的逻辑，第一处是单条路径不符合的话，返回false，第二处是如果所有的路径尝试后都没有返回true的话，就返回false。注意传入下层递归函数的值是已经减去节点后的值。

class Solution {
public:
    bool traversal(TreeNode* node,int curSum){
        if(!node->left&&!node->right&&curSum==0) return true;
        else if(!node->left&&!node->right&&curSum!=0) return false;
        //以上两个返回信息仅用于递归时
        if(node->left){
            curSum-=node->left->val;
            if(traversal(node->left,curSum)) return true;//下面的孩子节点告诉当前节点存在路径，那就继续向上返回true的信息
            curSum+=node->left->val;
        }
        if(node->right){
            curSum-=node->right->val;
            if(traversal(node->right,curSum)) return true;
            curSum+=node->right->val;
        }
        return false;
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(!root) return false;
        return traversal(root,targetSum-root->val);
    }
};

113.路径总和ii

注意终止条件有两个，符合/不符合，然后注意在进行下一层递归之前path已经记录了节点的数值，传入递归函数的数也是减去后的数。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void traversal(TreeNode* node,int cursum){
        //终止条件有两个，一个是符合条件，一个是不符合条件
        if(!node->left&&!node->right&&cursum==0){
            res.push_back(path);
            return;
        }
        if(!node->left&&!node->right) return;
        if(node->left){
            path.push_back(node->left->val);
            cursum-=node->left->val;
            traversal(node->left,cursum);
            cursum+=node->left->val;
            path.pop_back();
        }
        if(node->right){
            path.push_back(node->right->val);
            cursum-=node->right->val;
            traversal(node->right,cursum);
            cursum+=node->right->val;
            path.pop_back();
        }
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        res.clear();
        path.clear();
        if(!root) return res;
        path.push_back(root->val);
        traversal(root,targetSum-root->val);
        return res;
    }
};

106.从中序与后序遍历序列构造二叉树 

1、如果后序数组的元素个数为0，则返回NULL

2、如果不为空，取后序数组最后一个元素为根节点的值

3、找到后序数组最后一个元素在中序数组中的位置

4、切中序数组

5、切后序数组

6、递归构造二叉树

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(postorder.size()==0) return NULL;
        //如果不为空，取后序数组最后一个元素为节点元素
        int rootval=postorder[postorder.size()-1];
        TreeNode* root=new TreeNode(rootval);
        if(postorder.size()==1) return root;
        //找后序数组最后一个元素在中序数组中的位置，作为切割点
        int idx;
        for(idx=0;idx<inorder.size();idx++){
            if(inorder[idx]==rootval) break;
        }
        //切中序数组
        vector<int> leftinorder(inorder.begin(),inorder.begin()+idx);
        vector<int> rightinorder(inorder.begin()+idx+1,inorder.end());
        //切后序数组
        postorder.resize(postorder.size()-1);
        vector<int> leftpostorder(postorder.begin(),postorder.begin()+leftinorder.size());
        vector<int> rightpostorder(postorder.begin()+leftinorder.size(),postorder.end());
        root->left=buildTree(leftinorder,leftpostorder);
        root->right=buildTree(rightinorder,rightpostorder);
        return root;
    }
};

105.从前序与中序遍历序列构造二叉树

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size()==0) return NULL;
        int rootval=preorder[0];
        TreeNode* root=new TreeNode(rootval);
        if(preorder.size()==1) return root;
        int index;
        for(index=0;index<inorder.size();index++){
            if(inorder[index]==preorder[0]) break;
        }
        vector<int> leftinorder(inorder.begin(),inorder.begin()+index);
        vector<int> rightinorder(inorder.begin()+index+1,inorder.end());
        
        vector<int> leftpreorder(preorder.begin()+1,preorder.begin()+leftinorder.size()+1);
        vector<int> rightpreorder(preorder.begin()+leftinorder.size()+1,preorder.end());
        root->left=buildTree(leftpreorder,leftinorder);
        root->right=buildTree(rightpreorder,rightinorder);
        return root;
    }
};

划分左中序区间的时候边界问题出错。