(第32天) 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