代码随想录算法训练营打卡Day18 | LeetCode513 找树左下角的值、LeetCode112 路径总和、LeetCode106 从中序与后序遍历构造二叉树

摘要

前序遍历自上而下的逻辑才是真正求二叉树各个节点深度的逻辑。
中序是结合前序或后序还原二叉树的关键

LeetCode513 找树左下角的值

初见题目的想法：
- 层序遍历，每遍历一层，只保存该层的第一个节点的值，直到遍历完二叉树，保存的就是树左下角的值

层序遍历的题解代码如下

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        if (root) que.push(root);

        int res = 0;
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                if (que.front()->left) que.push(que.front()->left);
                if (que.front()->right) que.push(que.front()->right);
                if (i == 0) res = que.front()->val;
                que.pop();
            }
        }

        return res;
    }
};

从另一个角度去考虑，树的左下角的节点也可以定义为：深度最大的，从左往右数的第一个节点。
采用递归法求解
- 递归终止条件为到叶节点，然后判断叶节点的深度是否大于当前最大深度：大于，则保存该叶节点的值；否则直接返回。
- depth > maxDepth求的是第一个达到最大深度的节点，即我们要的“左下角”；
- 讲条件改为depth >= maxDepth，则求的是最后一个到达最大深度的节点，即“右下角”

可以理解为先序遍历，先判断当前节点是否为叶节点，然后再去访问左子树和右子树。

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

LeetCode112 路径总和

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

初见题目的想法，通过回溯和递归来枚举每条到叶节点的路径的和，再与目标值做比较
这道题的递归函数既可以返回bool值，也可以通过传引用来保存答案。
- 我个人的习惯是将需要递归解决的问题分为两个函数，这个习惯来源于数据结构C++语言版第二版（清华大学出版社）这本教材的一些代码实现示例
- 驱动函数（Driver）：接收问题的参数，返回问题的答案。在驱动函数中声明各层递归共享的变量可以减少全局变量的使用，以及进行一些边界条件、空指针等的判断。
- 工作函数（WorkPlace）：在参数列表中，各层递归共享的变量为传引用&，需要回溯的变量为传拷贝值。在这里，各层递归共享的变量为是否找到targetSum，sum为需要回溯的变量。如果是比较复杂的对象如vector、stack等需要回溯，也可以传引用然后手动回溯的方式来提高性能。
- 将递归函数分为驱动函数和工作函数，可以隐藏递归的内部实现，同时提供的函数接口也更简洁易用。同时，我个人认为，这样实现递归函数也充分利用了C++的语言特性，充分利用了传值和传引用的区别。
- 但也有缺点，工作函数的参数列表可能会很长。

完整的题解代码如下，无返回值的递归函数。

class Solution {
public:
    // WorkPlace
    void hasPathSumWorkPlace(TreeNode* cur, int sum, int& targetSum, bool& res) {
        sum += cur->val;
        if (!cur->left && !cur->right){
            if (sum == targetSum) {
                res = true;
            }
            return;// 只需要找到一个相等的值就可以了，所以直接返回
        }
        if (cur->left) hasPathSumWorkPlace(cur->left, sum, targetSum, res);
        if (cur->right) hasPathSumWorkPlace(cur->right, sum, targetSum, res);
    }
    // Driver
    bool hasPathSum(TreeNode* root, int targetSum) {
        bool res = false;
        int sum = 0;
        if (root) hasPathSumWorkPlace(root, sum, targetSum, res);
        return res;
    }
};

看了讲解后写了一遍递归函数有返回值的版本，以便对比学习

class Solution {
private:
    bool traversal(TreeNode* cur, int count) {
        if (!cur->left && !cur->right && count == 0) return true; // 遇到叶子节点，并且计数为0
        if (!cur->left && !cur->right) return false; // 遇到叶子节点直接返回

        if (cur->left) {
            count -= cur->left->val; // 递归，处理节点;
            if (traversal(cur->left, count)) return true;
            count += cur->left->val; // 回溯，撤销处理结果
        }
        if (cur->right) {
            count -= cur->right->val; // 递归，处理节点;
            if (traversal(cur->right, count)) return true;
            count += cur->right->val; // 回溯，撤销处理结果
        }
        return false;
    }

public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (!root) return false;
        return traversal(root, sum - root->val);
    }
};

LeetCode113 路径总和II

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

两道题连着的，用递归函数无返回值版本的代码修改一下即可保存题目要求的路径。

完整的题解代码如下

class Solution {
public:
    // WorkPlace
    void pathSumWorkPlace(TreeNode* cur, int sum, int& targetSum,
                         vector<int>& path,
                         vector<vector<int>>& res) 
    {
        sum += cur->val;
        path.push_back(cur->val);
        if (!cur->left && !cur->right){
            if (sum == targetSum) {
                res.push_back(path);
            }
            return;
        }
        if (cur->left) {
            pathSumWorkPlace(cur->left, sum, targetSum, path, res);
            path.pop_back();// 传引用的参数要手动回溯
        }
        if (cur->right) {
            pathSumWorkPlace(cur->right, sum, targetSum, path, res);
            path.pop_back();// 手动回溯
        }
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> res;
        int curSum = 0;
        vector<int> path;
        if (root) pathSumWorkPlace(root, curSum, targetSum, path, res);
        return res;
    }
};

LeetCode106 从中序与后序遍历构造二叉树

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

由中序遍历的节点序列和后序遍历的节点序列，可以唯一确定一棵二叉树。中序和前序也可以唯一确定一棵二叉树。
用节点序列还原的关键是中序，因为
- 前序的第一个节点或后序的最后一个节点必定是根节点
- 由前序或后序求得的根节点，可以在中序中，将中序的序列划分为两部分，左边部分对应左子树的中序序列，右边部分对应右子树的中序序列。
- 而中序的两个子序列，分别和前序或后序中对应的左子树的序列和右子树的序列的长度是一样的。所以由中序划分出的两个子序列，又可以从前序或后序中划分出左子树的序列和右子树的序列。
- 上述过程是可以递归的，所以就可以由前/后序和中序来构造一棵二叉树
代码随想录的讲解用的是左闭右开区间，我自己写了一份左闭右闭区间的代码，以便对比
- 复习循环不变量原则，坚持自己对区间的定义，左闭右开就一直左闭右开，左闭右闭就一直左闭右闭
  
  例子
以上过程具体到递归实现，可以分为以下六步，
- 一、判断子区间是否不存在值：左闭右闭区间为l > r（l == r是合法的，区间内有一个值）；左闭右开区间为l == r，[l, r)，没有一个数能既等于l又不等于l。
- 二、判断子区间是否只有一个值：只有一个值，说明当前节点为叶节点，不需要再向下递归，可以直接返回了。
- 三、取后序的最后一个节点作为当前子树的根节点
- 四、找到根节点在中序序列中的位置，划分出左子树的中序序列和右子树中序序列
- 五、从后序序列中划分出左子树的后序序列和右子树的后序序列：左子树的中序序列和左子树的中序序列长度相等，右子树同理
- 六、递归处理左子树和右子树

左闭右闭区间的题解代码

class Solution {
public:
    TreeNode* buildTreeWorkPlace(vector<int>& inorder, pair<int, int> in,
                                 vector<int>& postorder, pair<int, int> post) 
    {
        if (post.first > post.second) return nullptr;
        TreeNode* root = new TreeNode(postorder[post.second]);
        if (post.first == post.second) return root;
        int delim = 0;
        for (auto& iter : inorder) {
            if (iter == root->val) break;
            delim++;
        }
        
        root->left = buildTreeWorkPlace(inorder, {in.first, delim - 1}, 
                                        postorder, {post.first, post.first + delim - in.first - 1});
        
        root->right = buildTreeWorkPlace(inorder, {delim + 1, in.second}, 
                                        postorder, {post.first + delim - in.first, post.second - 1});
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        TreeNode* root = nullptr;
        if (postorder.size()) 
            root = buildTreeWorkPlace(inorder, {0, inorder.size() - 1}, 
                                    postorder, {0, postorder.size() - 1});
        return root;
    }
};