- VisualStudio2022插件的安装及使用-编程手把手系列文章
- pprof-在现网场景怎么用
- C#实现的下拉多选框,下拉多选树,多级节点
- 【学习笔记】基础数据结构:猫树
给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值.
假设二叉树中至少有一个节点.
输入: root = [2,1,3]
输出: 1
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
二叉树的节点个数的范围是 [1,10^4] -2^31 <= Node.val <= 2^31 - 1 。
这题我们有递归和迭代两种写法,我们在这里重点介绍递归的解法,如果用层序遍历的迭代法的话,我们这道题就十分简单了,不过我在后面也会介绍层序遍历的写法.
递归法我们一定要清楚的是三点:
其实本题当中递归里面也蕴含着回溯的逻辑,其实所有的递归算法都离不开回溯,只是我们没有意识到回溯的过程,或者说回溯的过程被隐藏掉了.
下面的代码中我会重点强调回溯的逻辑 。
这题的参数,既然是要求最后一层的最左边的节点,那么我们必然要使用一个参数depth来表示深度,然后我们也需要一个参数maxdepth来表示当前是否是达到了最大的深度,不过这个maxdepth变量不需要 。
传入函数中,我们可以定义为全局变量,如果depth>maxdepth,就证明当前还未到达最大深度,也就不是我们要处理的最左边的节点了。 同时,我们还需要一个参数result来接收我们需要求得这个节点的节点 。
值,这个变量我们也定义为全局变量.
我们要处理的是什么节点?是不是叶子节点,我们处理叶子节点的逻辑判断是什么?是不是只需要当前这个节点它的左右孩子都为空的时候,我们就到达了我们需要处理的时候了,这个时候就是返回的时候了.
那我们要处理这个节点,要做些什么事情呢?——我们要判断当前深度是否是最大深度,如果不是,我们就得更新这个最大深度,同时我们要更新result变量的值,然后再返回,这样就处理好了递归的边界条件, 。
对吧?
这段逻辑的代码如下:
//处理到叶子节点就返回
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--;
}
其实,处理好了这几个边界条件,我们的代码就出来了 。
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;
}
};
其实,这题使用层序遍历才是最方便,最简单的做法。我们只需要处理每一层的第一个元素,然后处理到最后一层,它自然就是最后一层的左边第一个元素了,这题只需要在层序遍历的模板上面改动一点点 。
就可以实现了! 。
如果不会层序遍历的话,推荐去看看我的层序遍历的文章,里面详细讲解了层序遍历实现的过程! 。
层序遍历:https://www.cnblogs.com/Tomorrowland/p/18318744 。
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) 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;
}
};
最后此篇关于LeetCode513.找树左下角的值的文章就讲到这里了,如果你想了解更多关于LeetCode513.找树左下角的值的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
例如,我有一个父类Author: class Author { String name static hasMany = [ fiction: Book,
代码如下: dojo.query(subNav.navClass).forEach(function(node, index, arr){ if(dojo.style(node, 'd
我有一个带有 Id 和姓名的学生表和一个带有 Id 和 friend Id 的 Friends 表。我想加入这两个表并找到学生的 friend 。 例如,Ashley 的 friend 是 Saman
我通过互联网浏览,但仍未找到问题的答案。应该很容易: class Parent { String name Child child } 当我有一个 child 对象时,如何获得它的 paren
我正在尝试创建一个以 Firebase 作为我的后端的社交应用。现在我正面临如何(在哪里?)找到 friend 功能的问题。 我有每个用户的邮件地址。 我可以访问用户的电话也预订。 在传统的后端中,我
我主要想澄清以下几点: 1。有人告诉我,在 iOS 5 及以下版本中,如果您使用 Game Center 设置多人游戏,则“查找 Facebook 好友”(如与好友争夺战)的功能不是内置的,因此您需要
关于redis docker镜像ENTRYPOINT脚本 docker-entrypoint.sh : #!/bin/sh set -e # first arg is `-f` or `--some-
我是一名优秀的程序员,十分优秀!