当前位置：首页 > news >正文

算法力扣刷题记录四十八【513.找树左下角的值】

news 来源：原创 2024/9/20 21:34:30

前言

二叉树篇继续。
记录四十八【513.找树左下角的值】

一、题目阅读

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

假设二叉树中至少有一个节点。

示例 1:
在这里插入图片描述

输入: root = [2,1,3]
输出: 1

示例 2:
在这里插入图片描述

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

提示:

二叉树的节点个数的范围是 [1,104]
-2^31 <= Node.val <= 2^31 - 1

二、尝试实现

找最底层最左边的节点，依然要遍历树。
（1）确定遍历顺序：前序。因为需要获得最大深度，从上到下获取深度，使用前序遍历（中左右）。
（2）使用递归实现：那么按步骤确定。

确定参数：需要传入节点——TreeNode* cur；需要传入深度——int depth，不是引用，为了方便回溯使用副本；需要记录结果——int& result，这是引用，方便替换值，所以不使用副本。
确定返回值：结果在参数result中有记录，所以不需要返回值了。
确定终止条件：当遇到叶子节点可以return。遇到叶子节点还有处理逻辑：
- 判断这个叶子节点的深度是不是记录的最大深度。如果是，更新当前遍历的最大深度，同时更新result。因为中左右的顺序，如果是更深的一层，肯定是最左边的叶子。
确定逻辑：
- 中：不用处理什么；
- 左：如果cur->left存在，深入遍历，传递depth+1；
- 右：如果cur->right存在，深入遍历，传递depth+1；和左的逻辑一样。

代码实现【递归】

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int maxdepth = 1;//记录当前遍历的最大深度void traversal(TreeNode* cur,int depth,int& result){if(!cur->left && !cur->right){//叶子节点if(depth > maxdepth){maxdepth = depth;result = cur->val;}return;}if(cur->left){traversal(cur->left,depth+1,result);}if(cur->right){traversal(cur->right,depth+1,result);}}int findBottomLeftValue(TreeNode* root) {int result;traversal(root,1,result);return result;}
};

三、参考学习

参考学历链接

学习内容

概念确定：左下角的值——最后一层最左边的值。
递归思路：深度最大就是最后一行；最左边：涉及遍历顺序。前中后都可以。

遍历顺序原因：因为中没有处理逻辑，所以只要左在右的前面就好；前序（中左右）、中序（左中右）、后序（左右中）都是左在右的前面。
注意：depth要回溯。

递归代码实现：就是二、中的代码实现。
迭代思路：遍历到一层，先把这一层第一个节点记录下来；后面还有新的层，就替换新一层的第一个节点；那么记录的结果就是最后一层的第一个节点。

迭代代码实现：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int findBottomLeftValue(TreeNode* root) {int result;queue<TreeNode*> q;q.push(root);while(!q.empty()){int size = q.size();for(int i = 0;i < size;i++){TreeNode* cur = q.front();q.pop();if(i == 0){result = cur->val;}if(cur->left) q.push(cur->left);if(cur->right) q.push(cur->right);}}return result;}
};