ToB企服应用市场:ToB评测及商务社交产业平台

标题: LeetCode513. 找树左下角的值 [打印本页]

作者: 雁过留声 时间: 2024-7-25 14:24
标题: LeetCode513. 找树左下角的值
题目链接：https://leetcode.cn/problems/find-bottom-left-tree-value/description/

题目叙述：

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

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

复制代码

示例 2:

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

复制代码

提示:

二叉树的节点个数的范围是 [1,10^4]
-2^31 right==NULL){ if(depth>maxdepth){ maxdepth=depth; result=cur->val; } return; }[/code]单层递归的逻辑

我们现在找到了最深层次的叶子节点，那么我们如何包管它一定是最左边的节点呢？那还不简朴嘛！只必要我们处理递归的时候，优先处理左子树，不就能包管我们先处理的是左孩子了嘛！对吧，
这段逻辑的代码如下：

//处理到叶子节点就返回
if(cur->left==NULL&&cur->right==NULL){
if(depth>maxdepth){
maxdepth=depth;
result=cur->val;
}
return;
}

复制代码

其实，处理好了这几个界限条件，我们的代码就出来了
整体代码：

class Solution {public: int result=0; int maxdepth=INT_MIN; void traversal(TreeNode*cur,int depth){ //处理到叶子节点就返回 if(cur->left==NULL&&cur->right==NULL){ if(depth>maxdepth){ maxdepth=depth; result=cur->val; } return; } //处理到叶子节点就返回
if(cur->left==NULL&&cur->right==NULL){
if(depth>maxdepth){
maxdepth=depth;
result=cur->val;
}
return;
} } int findBottomLeftValue(TreeNode* root) { traversal(root,0); return result; }};

复制代码

层序遍历（迭代法）

其实，这题使用层序遍历才是最方便，最简朴的做法。我们只必要处理每一层的第一个元素，然后处理到末了一层，它自然就是末了一层的左边第一个元素了，这题只必要在层序遍历的模板上面改动一点点
就可以实现了！
假如不会层序遍历的话，推荐去看看我的层序遍历的文章，内里详细讲授了层序遍历实现的过程！
层序遍历：https://www.cnblogs.com/Tomorrowland/p/18318744

class Solution {
public:
int result=0;
int maxdepth=INT_MIN;
void traversal(TreeNode*cur,int depth){
//处理到叶子节点就返回
if(cur->left==NULL&&cur->right==NULL){
if(depth>maxdepth){
maxdepth=depth;
result=cur->val;
}
return;
}
if(cur->left!=NULL){
//先让depth++，让他处理下一层的节点
depth++;
traversal(cur->left,depth);
//再让depth--，这就是回溯的过程，退到上一层的节点，再处理右边的子树
depth--;
}
if(cur->right!=NULL){
//这里也是一样的道理
depth++;
traversal(cur->right,depth);
//这里也是回溯的过程
depth--;
}
}
int findBottomLeftValue(TreeNode* root) {
traversal(root,0);
return result;
}
};

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)