算法训练营第二十一天 | LeetCode 513 找树左下角的值、LeetCode 112 路径总和、LeetCode 106 从中序与后序遍历构造二叉树

LeetCode 513 找树左下角的值

这题要求找树最底层最左边节点的值，用单纯的迭代法、递归法都不太好处理，一般的层序遍历法也不太行。但是可以修改下层序遍历，改成每一层从右往左遍历，依次往下，这样子访问的最后一个节点就是最底层最左边的节点了。这也用到了广度优先搜索的方法。

代码如下：

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> myque;
        TreeNode* cur = root;
        myque.push(root);
        while (!myque.empty()) {
            int num = myque.size();
            while (num--) {
                cur = myque.front();
                myque.pop();
                if (cur->right) myque.push(cur->right);
                if (cur->left) myque.push(cur->left);
            }
        }
        return cur->val;
    }
};

深度优先搜索是递归的改版。之后有时间再写下。

LeetCode 112 路径总和

和昨天一样的回溯法

class Solution {
private:
    int num = 0;
    int sum = 0;
public:
    void backtracking(TreeNode* cur, int targetSum) {
        if (!cur->left && !cur->right) {
            if (sum == targetSum) num++;
            return;
        }
        if (cur->left) {
            sum += cur->left->val;
            backtracking(cur->left, targetSum);
            sum -= cur->left->val;
        }
        if (cur->right) {
            sum += cur->right->val;
            backtracking(cur->right, targetSum);
            sum -= cur->right->val;
        }
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;
        targetSum -= root->val;
        backtracking(root, targetSum);
        return (bool)num;
    }
};

也可以像求高度一样用递归。这里就不写了。

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

这题感觉确实是有难度了。首先是对于中序遍历和后序遍历确定一棵树的理解，其次是递归时递归逻辑的选择和确定。还可以用map降低时间复杂度，以及要注意先递归构建右子树，再递归构建左子树，这样方便从后往前地从后序遍历中取数作为根节点查找依据。之所以这样也是因为迭代法求后序遍历时所收获的一些感悟和心得——后续遍历是中右左遍历方式的反转，每次放入的节点一定先是局部状态下的根节点，后是局部状态下的右节点，再是局部状态下的左节点。

代码如下：

class Solution {
public:
    TreeNode* mybuildTree(vector<int>& inorder, int in_l, int in_r, 
    vector<int>& postorder, int post_l, int post_r) {
        if (in_l > in_r) return nullptr;
        // if (in_l == in_r) {
        //     TreeNode* newNode = new TreeNode(inorder[in_l]);
        //     return newNode;
        // }
        int rootval = postorder[post_r];
        int in_rootIndex = 0;
        for (int i = in_l; i <= in_r; i++) {
            if (inorder[i] == rootval) {
                in_rootIndex = i;
                break;
            }
        }
        TreeNode* root = new TreeNode(rootval);
        if (in_rootIndex > in_l) {
            root->left = mybuildTree(inorder, in_l, in_rootIndex -1, postorder, post_l, post_l + (in_rootIndex - 1-in_l));
        }
        if (in_r > in_rootIndex) {
            int first_r = inorder[in_rootIndex + 1];
            int post_rstart = 0;
            for (int i = post_l; i <= post_r; i++) {
                if (postorder[i] == first_r) {
                    post_rstart = i;
                    break;
                }
            }
            root->right = mybuildTree(inorder, in_rootIndex + 1, in_r, postorder, post_rstart, post_r - 1);
        }
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return mybuildTree(inorder, 0, inorder.size() - 1, postorder, 0, inorder.size() - 1);
    }
};

中间四行不注释掉会报错。