代码随想录第二十天 | 513. 找树左下角的值，路径总和，106. 从中序与后序遍历序列构造二叉树

513. 找树左下角的值 

第一想法：感觉用层序遍历比用递归遍历容易很多，层序遍历好久没写了，先试试。只会写遍历模板，其余的不太会写了...

看完想法：层序遍历还是复习一下。在que.push(root)前，先验证一下root是否为空。并用一个vector<vector<int>> vec 和 vector<int> tmp分别存储层序遍历后的二叉树和每层的二叉树。按照模板更改的话，只需要记录每行的第一个元素就可以了，到最后就会覆盖成最后一行的第一个的。在往深层遍历时，应该选用记录front的变量去递归，而不是root

递归想法：建立两个全局变量，一个存储最大深度，一个存储最大深度的最大值，然后使用回溯

//层序遍历法
int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        if(root != nullptr) que.push(root);
        int result = 0;
        while(!que.empty()){
            int size = que.size();//每层的大小是不一样的
            
            for(int i = 0; i< size; i++){
                TreeNode* tmp = que.front();
                que.pop();
                if(i == 0 ) result =  tmp->val;
                if(tmp->left) que.push(tmp->left);
                if(tmp->right) que.push(tmp->right);
            }
        }
        return result;

    }

class Solution {
public:
    int maxDepth = INT_MIN;
    int result;
    void traversal(TreeNode* root, int depth) {
        if (root->left == NULL && root->right == NULL) {
            if (depth > maxDepth) {
                maxDepth = depth;
                result = root->val;
            }
            return;
        }
        if (root->left) {
            depth++;
            traversal(root->left, depth);
            depth--; // 回溯
        }
        if (root->right) {
            depth++;
            traversal(root->right, depth);
            depth--; // 回溯
        }
        return;
    }
    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);
        return result;
    }
};

if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回

 在回溯中，遇到合适的路径要及时返回，如这里就是if(traversal) return true;

在路径搜索Ⅱ中，由于不需要对返回值作处理，所以递归函数的返回值是void

vector<vector<int>> result;
    vector<int> path;
    void traversal(TreeNode* root, int count){
        if(!root->left && !root->right && count==0){
            result.push_back(path);
        }
        if(!root->left && !root->right) return ;
        
        
        if(root->left){
            count-=root->left->val;
            path.push_back(root->left->val);
            traversal(root->left, count);
            count+=root->left->val;
            path.pop_back();
        }
        if(root->right){
            count-=root->right->val;
            path.push_back(root->right->val);
            traversal(root->right, count);
            count+=root->right->val;
            path.pop_back();
        }
    }


    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if(root==nullptr) return result;
        path.push_back(root->val);
        traversal(root, targetSum-root->val);
        return result;

    }

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

第一想法：