【算法训练营day18】LeetCode513. 找树左下角的值 LeetCode112. 路径总和 LeetCode113. 路径总和II LeetCode106. 从中序与后序遍历序列构造二叉树

LeetCode513. 找树左下角的值

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

初次尝试

后序递归法，传递一个容器保存当前节点的高度和当前节点为根的树左下角的值，递归单层逻辑是如果左子树节点高度不小于右子树，则返回左子树的容器，反之返回右子树的容器。

class Solution {
public:
    vector<int> findValue(TreeNode* node) {
        if (node == NULL) return {0, 0};
        if (node -> left == NULL && node -> right == NULL) return {1, node -> val};
        vector<int> left_vec = findValue(node -> left);
        vector<int> right_vec = findValue(node -> right);
        if (left_vec[0] >= right_vec[0]) return {left_vec[0] + 1, left_vec[1]};
        else return {right_vec[0] + 1, right_vec[1]};
    }

    int findBottomLeftValue(TreeNode* root) {
        return findValue(root)[1];
    }
};

看完代码随想录后的想法

前序递归回溯法也可以解，当然使用层序迭代法是最简单最合适的，题解代码如下。

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        int result = 0;
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (i == 0) result = node->val; // 记录最后一行第一个元素
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return result;
    }
};

LeetCode112. 路径总和

题目链接：112. 路径总和

初次尝试

使用的是带回溯的递归法，遇到叶子节点后判断路径和是否与目标值相等，代码写的比较完整且直观，有不少简化空间。

class Solution {
public:
    bool pathSum(TreeNode* node, int sum, int targetSum) {
        if (node -> left == NULL && node -> right == NULL) {
            if ((sum += node -> val) == targetSum) {
                return true;
            }
        }
        bool left_bool = false;
        bool right_bool = false;
        if (node -> left) {
            sum += node -> val;
            left_bool = pathSum(node -> left, sum, targetSum);
            sum -= node -> val;
        }
        if (node -> right) {
            sum += node -> val;
            right_bool = pathSum(node -> right, sum, targetSum);
            sum -= node -> val;
        }
        return left_bool || right_bool;
    }

    bool hasPathSum(TreeNode* root, int targetSum) {
        int sum = 0;
        if (root) return pathSum(root, sum, targetSum);
        else return false;
    }
};

看完代码随想录后的想法

如下所示，上述代码还有很多地方可以优化。

不要去累加然后判断是否等于目标和，那么代码比较麻烦，可以用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。

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 == NULL) return false;
        return traversal(root, sum - root->val);
    }
};

LeetCode113. 路径总和II

题目链接：113. 路径总和II

初次尝试

递归带回溯法，吸取了上一题题解的思路，一遍ac。

class Solution {
public:
    void sumPath(TreeNode* node, int count, vector<int> temp, vector<vector<int>>& ans) {
        if (!node -> left && !node -> right && count == 0) ans.push_back(temp);

        if (node -> left) {
            count -= node -> left -> val;
            temp.push_back(node -> left -> val);
            sumPath(node -> left, count, temp, ans);
            temp.pop_back();
            count += node -> left -> val;
        }
        if (node -> right) {
            count -= node -> right -> val;
            temp.push_back(node -> right -> val);
            sumPath(node -> right, count, temp, ans);
            temp.pop_back();
            count += node -> right -> val;
        }
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if (root) {
            int count = targetSum;
            vector<int> temp;
            vector<vector<int>> ans;
            temp.push_back(root -> val);
            sumPath(root, count - root -> val, temp, ans);
            return ans;
        }
        else return {};
    }
};

看完代码随想录后的想法

思路差不多。

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

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

初次尝试

没有想到什么好的思路。

看完代码随想录后的想法

题解思路大概是：

1. 后序数组的最后一个元素值为根节点的值
2. 通过根节点分割中序数组，得到左子树和右子树的中序数组
3. 通过左子树中序数组的大小，分割后序数组，得到左子树和右子树的后序数组
4. 递归，得到左子树和右子树，返回根节点。

class Solution {
public:
    TreeNode* traversal(vector<int> inorder, vector<int> postorder) {
        if (postorder.size() == 0) return NULL;

        int root_value = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(root_value);

        if (postorder.size() == 1) return root;

        int delimiter_index;
        for (delimiter_index = 0; delimiter_index < inorder.size(); delimiter_index++) {
            if (inorder[delimiter_index] == root_value) break;
        }

        vector<int> left_inorder(inorder.begin(), inorder.begin() + delimiter_index);
        vector<int> right_inorder(inorder.begin() + delimiter_index + 1, inorder.end());

        vector<int> left_postorder(postorder.begin(), postorder.begin() + left_inorder.size());
        vector<int> right_postorder(postorder.begin() + left_inorder.size(), postorder.end() - 1);

        root -> left = traversal(left_inorder, left_postorder);
        root -> right = traversal(right_inorder, right_postorder);

        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return traversal(inorder, postorder);
    }
};