代码随想录-训练营-day14

513. 找树左下角的值 - 力扣（LeetCode）

又是一个具体去找二叉树的特定位置的值的题，这种题我们采用层序遍历的方法就非常方便，因为比起其他遍历的方法，层序遍历的方法需要我们进行一个层内的遍历，我们可以利用遍历的下标锁定到特定的位置。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> q;
        if(root)q.push(root);
        int res=root->val;
        while(!q.empty()){
            int n=q.size();
            for(int i=0;i<n;i++){
                TreeNode* node=q.front();
                q.pop();
                if(i==0)res=node->val;
                if(node->left)q.push(node->left);
                if(node->right)q.push(node->right);
            }
        }
        return res;
    }
};

112. 路径总和 - 力扣（LeetCode）

这题我们需要去挨个遍历我们的路径并计算路径总和是否等于我们的targetSum并返回bool值。

思路上来说，我们首先需要去遍历所有的路径并计算每条路径的总和值，我们可以用一个栈来模拟遍历路径（其实本质上就是DFS），然后栈里同时存储我们遍历过的二叉树节点与当前路径的总和，最后当我们发现遍历到了叶子节点就检查路径总和是否满足要求即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        stack<pair<TreeNode*,int>> stk;
        if(root)stk.push({root,root->val});
        while(!stk.empty()){
            auto [node,num]=stk.top();
            stk.pop();
            if(!node->left&&!node->right&&num==targetSum)return true;
            if(node->left)stk.push({node->left,num+node->left->val});
            if(node->right)stk.push({node->right,num+node->right->val});
        }
        return false;
    }
};

113. 路径总和 II - 力扣（LeetCode）

这个题比起上一个题要求找出所有满足条件的路径，我们当然也可以用栈来模拟递归的DFS方法来做：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> res;
        if(!root)return res;
        stack<pair<TreeNode*,pair<int,vector<int>>>> stk;
        stk.push({root,{targetSum-root->val,{root->val}}});
        while(!stk.empty()){
            auto [node,state]=stk.top();
            stk.pop();
            int remain=state.first;
            vector<int> path=state.second;
            if(!node->left&&!node->right&&remain==0){
                res.push_back(path);
                continue;
            }
            if(node->left){
                vector<int> newpath=path;
                newpath.push_back(node->left->val);
                stk.push({node->left,{remain-node->left->val,newpath}});
            }
            if(node->right){
                vector<int> newpath=path;
                newpath.push_back(node->right->val);
                stk.push({node->right,{remain-node->right->val,newpath}});
            }
        }
        return res;
    }
};

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

我们需要根据中序和后序的遍历数组来构建二叉树，那么我们就需要一个哈希表来构建关系，让我们可以根据后序遍历来搭建中序遍历的二叉树。这里我们要想清楚中序的数组和后序的数组对于构建二叉树的作用：我们需要后序遍历来确定顺序，但是我们并不知道具体的二叉树的左右子树需要取的长度，所以我们需要用中序数组来确定。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map<int,int> mp;
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        for(int i=0;i<inorder.size();++i){
            mp[inorder[i]]=i;
        }
        return helper(inorder,postorder,0,inorder.size()-1,0,postorder.size()-1);
    }
    TreeNode* helper(vector<int>& inorder, vector<int>& postorder,int inleft,int inright,int postleft,int postright){
        if(postright<postleft)return nullptr;
        int postroot=postright;
        TreeNode* root=new TreeNode(postorder[postroot]);
        int inroot=mp[root->val];
        int size_right=inright-inroot;
        root->left=helper(inorder,postorder,inleft,inroot-1,postleft,postright-size_right-1);
        root->right=helper(inorder,postorder,inroot+1,inright,postright-size_right,postright-1);
        return root;
    }
};

与这个题比较类似的是从前序和中序遍历序列中构建二叉树。

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map<int,int> mp;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i=0;i<preorder.size();i++){
            mp[inorder[i]]=i;
        }
        return helper(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
    }
    TreeNode* helper(vector<int>& preorder, vector<int>& inorder,int preleft,int preright,int inleft,int inright){
        if(preleft>preright)return nullptr;
        int preroot=preleft;
        TreeNode* root=new TreeNode(preorder[preroot]);
        int inroot=mp[root->val];
        int size_left=inroot-inleft;
        root->left=helper(preorder, inorder, preleft+1, preleft+size_left, inleft, inroot-1);
        root->right=helper(preorder, inorder, preleft+size_left+1, preright, inroot+1, inright);
        return root;
    }   
};

今天的题总体来说还是偏难，需要多加练习进行掌握。