二刷代码随想录第16天

513. 找树左下角的值

• 找到深度最大的点，遍历方式左边节点在右边节点前面，找到就返回，一定就是最左下角的值了

class Solution {
public:
    int max_depth = -1;
    int result = 0;
    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);
        return result;
    }

    void traversal(TreeNode* node, int depth) {
        if (node->left == nullptr && node->right == nullptr) {
            if (depth > max_depth) {
                max_depth = depth;
                result = node->val;
                return;
            }
        }
        if (node->left) {
            depth++;
            traversal(node->left, depth);
            depth--;
        }
        if (node->right) {
            depth++;
            traversal(node->right, depth);
            depth--;
        }
    }
};

112. 路径总和

• 不需要求路径，需要返回一个bool值代表找没找到

class Solution {
public:
    int sum = 0;
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) {
            return false;
        }
        sum += root->val;
        if (root->left == nullptr && root->right == nullptr) {
            if (sum == targetSum) {
                return true;
            }
            return false;
        }
        if (root->left) {
            bool left = hasPathSum(root->left, targetSum);
            if(left){
                return true;
            }
            sum -= root->left->val;
        }
        if (root->right) {
            bool right = hasPathSum(root->right, targetSum);
            if(right){
                return true;
            }
            sum -= root->right->val;
        }
        return false;
    }
};

13. 路径总和 II

• 需要求路径，就不用返回值

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    int sum = 0;
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) {
            return result;
        }
        sum += root->val;
        path.push_back(root->val);
        get_path(root, targetSum);
        return result;
    }
    void get_path(TreeNode* node, int targetSum) {
        if (node->left == nullptr && node->right == nullptr) {
            if (sum == targetSum) {
                result.push_back(path);
            }
            return;
        }
        if (node->left) {
            sum += node->left->val;
            path.push_back(node->left->val);
            get_path(node->left, targetSum);
            sum -= node->left->val;
            path.pop_back();
        }
        if (node->right) {
            sum += node->right->val;
            path.push_back(node->right->val);
            get_path(node->right, targetSum);
            sum -= node->right->val;
            path.pop_back();
        }
        return;
    }
};

105. 从前序与中序遍历序列构造二叉树

• 重点是找到前序遍历的第一个节点，在中序遍历中把他一分为二，再把前序遍历剩下的节点也一分为二，不断重复这个过程

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() == 0) {
            return nullptr;
        }
        int val = preorder[0];
        int index = 0;
        for (int i = 0; i < inorder.size(); i++) {
            if (inorder[i] == val) {
                index = i;
            }
        }
        vector<int> left_preorder;
        vector<int> right_preorder;
        vector<int> left_inorder;
        vector<int> right_inorder;
        for (int i = 0; i < index; i++) {
            left_inorder.push_back(inorder[i]);
        }
        for (int i = index + 1; i < inorder.size(); i++) {
            right_inorder.push_back(inorder[i]);
        }
        for (int i = 1; i <= index; i++) {
            left_preorder.push_back(preorder[i]);
        }
        for (int i = index + 1; i < preorder.size(); i++) {
            right_preorder.push_back(preorder[i]);
        }
        TreeNode* node = new TreeNode(val);
        node->left = buildTree(left_preorder, left_inorder);
        node->right = buildTree(right_preorder, right_inorder);
        return node;
    }
};

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

• 重点是从后序遍历中找到最后一个节点，在中序遍历中把他一分为二，再把后序遍历的剩下的节点也一分为二，不断重复这个过程

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (postorder.size() == 0) {
            return nullptr;
        }
        int val = postorder[postorder.size() - 1];
        int index = 0;
        for (int i = 0; i < inorder.size(); i++) {
            if (inorder[i] == val) {
                index = i;
            }
        }
        TreeNode* node = new TreeNode(val);
        vector<int> left_inorder;
        vector<int> right_inorder;
        vector<int> left_postorder;
        vector<int> right_postorder;
        for (int i = 0; i < index; i++) {
            left_inorder.push_back(inorder[i]);
        }
        for (int i = index + 1; i < inorder.size(); i++) {
            right_inorder.push_back(inorder[i]);
        }
        for (int i = 0; i < index; i++) {
            left_postorder.push_back(postorder[i]);
        }
        for (int i = index; i < postorder.size() - 1; i++) {
            right_postorder.push_back(postorder[i]);
        }
        node->left = buildTree(left_inorder, left_postorder);
        node->right = buildTree(right_inorder, right_postorder);
        return node;
    }
};