立志重刷代码随想录60天冲冲冲！！——第十六天

513.找树左下角的值

层序遍历比较好想

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> res;

        if (root != nullptr) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);

                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            res.push_back(vec);
        }
        return res.back()[0];
    }
};

112. 路径总和

ture需要一层一层返回到最上面

需要用到回溯

需要最开始把头节点加进去

class Solution {
public:
    bool Traversal(TreeNode* node, int target) {
        if (node->left == nullptr && node->right == nullptr && target == 0) return true;
        if (node->left == nullptr && node->right == nullptr && target != 0) return false;

        if (node->left != nullptr) {
            target -= node->left->val;
            if (Traversal(node->left, target) == true) return true;
            target += node->left->val;
        }
        if (node->right != nullptr) {
            target -= node->right->val;
            if (Traversal(node->right, target) == true) return true;
            target += node->right->val;
        }
        return false;
    }

    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) return false; // 解决根节点空指针
        return Traversal(root, targetSum - root->val); // 解决根节点就是目标和的情况
    }
};

112. 路径总和二

需要最开始把头节点加进去

路径和目标和，都需要回溯

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void GetPath(TreeNode* node, int target) {
        if (!node->left && !node->right && target == 0) {
            res.push_back(path);
            return;
        }
        if (!node->left && !node->right && target != 0) return;

        if (node->left) {
            path.push_back(node->left->val);
            target -= node->left->val;
            GetPath(node->left, target);
            path.pop_back();
            target += node->left->val;
        }

        if (node->right) {
            path.push_back(node->right->val);
            target -= node->right->val;
            GetPath(node->right, target);
            path.pop_back();
            target += node->right->val;
        }
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) return res;
        path.push_back(root->val); // 必须先把根节点加入到路径中！！！
        GetPath(root, targetSum - root->val);
        return res;
    }
};

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

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

上面两题是同一类的。比较复杂，周末补更！！本周末任务艰巨，由之前落下的栈和队列两节，还有这道题