(第32天) 513、找树左下角的值 112、路径总和 113、路径总和II

目录

• 513、找树左下角的值
• • 题目描述
  • 思路
  • 代码
• 112、路径总和
• • 题目描述
  • 思路
  • 代码
• 113、路径总和II
• • 题目描述
  • 思路
  • 代码
• 思考
• 总结

513、找树左下角的值

题目描述

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。

思路

题目分析：

找到二叉树最底层的最左边节点。

迭代法：

• 使用层序遍历，在层序遍历过程中记录每一层的第一个节点值，结束之后，最后一个记录的节点值就是最底层最左侧的节点。

递归法：

• 递归函数设计目标：遍历二叉树，记录二叉树的最大深度及最大深度的最左节点的值。
• 参数：需要传递节点node用来遍历二叉树、需要depth用来记录遍历的深度。
• 返回值：无返回值，该函数只是记录最大深度和它最左节点的值。
• 终止条件：遇到叶子节点。这时需要通过条件判断进行最大深度和结果的更新。
• 递归逻辑：因为要求最底层最左侧节点，因此，只要先向左递归，再向右递归就可以。

代码

迭代法：

class Solution {
   
public:
    int findBottomLeftValue(TreeNode* root) {
   
        queue<TreeNode*> que;
        if (root != nullptr) 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;
    }
};

递归法：

class Solution {
   
public:
    int maxDepth = INT_MIN;//记录二叉树的最大深度
    int result;//记录结果
    void traversal(TreeNode* root, int depth) {
   
        if (root->left == nullptr && root->right == nullptr) {
   
            if (depth > maxDepth) {
   
                maxDepth = depth;//更新最大深度
                result = root->val;//更新最左侧节点值
            }
            return;
        }

        if (root->left) {
   
            depth++;
            traversal(root->left, depth);
            depth--;
        }
        if