补卡day16

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

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> qu;
      //  if(root == nullptr) return;
        TreeNode* node = nullptr;
        qu.push(root);
        while(!qu.empty()){
            int n = qu.size();
            while(n--){
                node = qu.front();
                qu.pop();
                if(node->right) qu.push(node->right);
                if(node->left) qu.push(node->left);
            }
        }
        return node->val; // 最后一个节点就是左下角的节点
    }
};

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

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
      if(root == nullptr) return false;
        targetSum -= root->val;
        // 如果现在已经是叶子节点了
        if(root->left == nullptr && root->right == nullptr){
            if(targetSum == 0){
                 return true;
            }else{
                return false;
            }
        }
        return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
    }
};

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

class Solution {
private:
    void dfs(TreeNode* node, int targetSum, vector<int> &path, vector<vector<int>>& res){
        if(node == nullptr) return;
        targetSum -= node->val;
        path.push_back(node->val);
        if(node->left == nullptr && node->right == nullptr){
            if(targetSum == 0){
                res.push_back(path); //共同使用一个path， 所以这里不能返回
                path.pop_back();
                return;
            }
        }
        dfs(node->left,targetSum,path,res);
        dfs(node->right,targetSum,path,res);
        path.pop_back();
    }
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<int> path;
        vector<vector<int>> res;
        dfs(root,targetSum,path,res);
       return res;
    }
};

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

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(postorder.empty()) return nullptr;// 空节点
        auto it = find(inorder.begin(), inorder.end(),postorder.back());
        int size = it - inorder.begin() ;
        vector<int> in1(inorder.begin(), inorder.begin() + size);//左子树的中序
        vector<int> in2(inorder.begin() + size + 1, inorder.end());// 右子树的中序
        vector<int> post1(postorder.begin(), postorder.begin() + size);//左子树的后序
        vector<int> post2(postorder.begin() + size, postorder.end() - 1);
        TreeNode* left = buildTree(in1, post1);
        TreeNode* right = buildTree(in2, post2);
        return new TreeNode(postorder.back(), left, right);
    }
};

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

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty()) return nullptr;
        auto it = find(inorder.begin(), inorder.end(), preorder.front());
        int size =  it - inorder.begin() ; // 左子树的大小
        vector<int> pre1(preorder.begin() + 1, preorder.begin() + size + 1); // 左子树的先序
        vector<int> pre2(preorder.begin() + size + 1, preorder.end());// 右子树的先序
        vector<int> in1(inorder.begin(), inorder.begin() + size);// 左子树的中序
        vector<int> in2(inorder.begin() + size + 1, inorder.end());
        TreeNode* left = buildTree(pre1, in1);
        TreeNode* right = buildTree(pre2, in2);
        return new TreeNode(preorder.front(), left, right);

    }
};