代码随想录算法训练营第十八天 | 513.找树左下角的值、112.路径总和、106.从中序与后序遍历序列构造二叉树

513.找树左下角的值

题目链接：513.找树左下角的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

文章讲解/视频讲解：https://programmercarl.com/0513.%E6%89%BE%E6%A0%91%E5%B7%A6%E4%B8%8B%E8%A7%92%E7%9A%84%E5%80%BC.html

思路

采用层序遍历的方式实现，记录下遍历每层时的第一个节点的值left_val，随着一层层地遍历，left_val的值也在不断更新，最终获得的left_val的值便是树的左下角的值。

看了卡哥的题解之后，也可以采用递归的方式来处理。要找到树左下角的值，即寻找树的最后一行的最左边的值。当采用前序遍历（中序或后序亦可）时，遍历到的每一行的第一个节点就是每一行最左边的节点。因此可以采用递归的前序遍历来解，在每次遍历时记录当前深度，如果当前深度比之前记录的最大深度要大，那么说明此时来到了新的一行，当前访问的节点为新的一行的最左边的节点。

C++实现

// 层序遍历求解
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        int left_val = -1;
        que.push(root);
        while(!que.empty()){
            int q_size = que.size();
            for(int i = 0;i<q_size;i++){
                TreeNode* cur = que.front();
                que.pop();
                if(i == 0) left_val = cur->val;
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
        }

        return left_val;
    }
};
// 前序递归遍历求解
class Solution {
public:
    int maxDepth;
    int leftBottom;
    int findBottomLeftValue(TreeNode* root) {
        maxDepth = numeric_limits<int>::min();
        dfs(root, 1);
        return leftBottom;
    }

    void dfs(TreeNode* node, int depth){
        if(depth > maxDepth){
            maxDepth = depth;
            leftBottom = node->val;
        }

        if(node->left) dfs(node->left, depth + 1);
        if(node->right) dfs(node->right, depth + 1);
    }
};

112.路径总和

题目链接：112.路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

文章讲解/视频讲解：https://programmercarl.com/0112.%E8%B7%AF%E5%BE%84%E6%80%BB%E5%92%8C.html

思路

用递归的方式来处理，递归函数携带当前已经累计的和，以及目标和，如果当前节点为叶子节点，且累计和与当前节点的值相加等于目标和，则说明找到了一个这样的节点，返回true。否则返回false。

也可以用迭代的方式来处理，用栈来模拟前序遍历，不过这时栈不仅要记录该节点指针，还要记录从头节点到该节点的路径数值总和。

C++实现

// 递归实现
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        return traversal(root, 0, targetSum);
    }

    bool traversal(TreeNode* node, int curSum, const int& targetSum){
        if(node == nullptr) return false;
        if(node->left == nullptr && node->right == nullptr){
            if(curSum + node->val == targetSum){
                return true;
            }
        }
        
        bool leftSuccess = traversal(node->left, curSum + node->val, targetSum);
        bool rightSuccess = traversal(node->right, curSum + node->val, targetSum);
        return leftSuccess || rightSuccess;
    }
};

// 迭代实现
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        stack<pair<TreeNode*, int>> stk;
        if(root == nullptr) return false;
        stk.push({root, root->val});

        while(!stk.empty()){
            auto cur = stk.top();
            stk.pop();
            if(!cur.first->left && !cur.first->right && cur.second == targetSum){
                return true;
            }
            if(cur.first->right){
                stk.push({cur.first->right, cur.second + cur.first->right->val});
            }
            if(cur.first->left){
                stk.push({cur.first->left, cur.second + cur.first->left->val});
            }
        }
        return false;
    }
};

顺便解决113.路径总和II

思路：

依然采用递归的思路，按照上题的方法，找到一条路径和等于目标和的路径，就加入结果中。

C++实现：

class Solution {
public:
    vector<vector<int>> results;
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<int> paths;
        traversal(root, 0, targetSum, paths);
        return results;
    }

    void traversal(TreeNode* node, int curSum, const int& targetSum, vector<int>& paths){
        if(node == nullptr) return;
        paths.push_back(node->val);
        if(!node->left && !node->right){
            if(curSum + node->val == targetSum) results.push_back(paths);
        }
        else{
            traversal(node->left, curSum + node->val, targetSum, paths);
            traversal(node->right, curSum + node->val, targetSum, paths);
        }
        paths.pop_back();
    }
};

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

题目链接：106.从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

文章讲解/视频讲解：https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html

思路

用递归的方法来做。递归函数traversal返回的是已经建立的子树的头节点，参数为包含该子树的inorder数组的范围$[l_1,r_1]$，包含该子树的postorder数组的范围$[l_2,r_2]$。

• 在每一次递归中，首先利用postorder数组找到头节点的值，当前范围的最后一个元素就是头节点，即下标$r_2$处，根据头节点的值建立节点。

• 通过头节点的值在inorder数组中找到左右子树的分界，即，头节点左边的元素都属于左子树，右边的元素都属于右子树。

• 通过在inorder数组中找到的左右子树分界，划分postorder数组中左右子树的分界，即，在inorder中找到左子树的节点个数size，postorder数组中$[l_2,l_2+size?1]$属于左子树，$[l_2+size,r_2?1]$属于右子树。

递归处理当前节点的左右子树，并把当前节点的left指向左子树，right指向右子树。

C++实现

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return traversal(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
    }

    TreeNode* traversal(const vector<int>& inorder, const vector<int>& postorder, int l1, int r1, int l2, int r2){
        if(l1 > r1) return nullptr;

        int headVal = postorder[r2];
        TreeNode* head = new TreeNode(headVal);
        int i;
        for(i = l1;i<=r1;i++){
            if(inorder[i] == headVal) break;
        }

        head->left = traversal(inorder, postorder, l1, i - 1, l2, l2 + i - l1 - 1);
        head->right = traversal(inorder, postorder, i + 1, r1, l2 + i - l1, r2 - 1);
        return head;
    }
};

与此题类似的还有另外一道题，105. 从前序与中序遍历序列构造二叉树

思路：与上一题类似，也是采用递归的思路，在每一次递归的过程中，头节点为前序序列当前范围的第一个元素。

C++实现：

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return traversal(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }

    TreeNode* traversal(const vector<int>& preorder, const vector<int>& inorder, int l1, int r1, int l2, int r2){
        if(l1 > r1) return nullptr;
        int headVal = preorder[l1];
        TreeNode* head = new TreeNode(headVal);

        int i;
        for(i = l2;i<=r2;i++){
            if(inorder[i] == headVal) break;
        }

        head->left = traversal(preorder, inorder, l1 + 1, l1 + i - l2, l2, i - 1);
        head->right = traversal(preorder, inorder, l1 + i - l2 + 1, r1, i + 1, r2);
        return head;
    }
};