LeetCode笔记:104.Maximum Depth of Binary Tree
2023-03-15 23:22:47 时间
问题:
Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
大意:
给出一个二叉树,找到其最大的深度。 最大深度是指从根节点到最远的叶子节点的最长距离的节点数。
思路:
要探索二叉树的深度,用递归比较方便。我们题目要求的函数返回根节点的深度,那么就做到对二叉树上每个节点调用此函数都返回其作为根节点看待时的深度。比如,所有叶子节点的深度都是1,再往上就是2、3...一直到root根节点的返回值就是最大的深度。 对于每个节点,我们先判断其本身是否是节点,如果是一个空二叉树,那么就应该返回0。 然后,我们定义两个变量,一个左节点深度,一个右节点深度。我们分别判断其有无左节点和右节点,两种节点中的做法都是一样的,假设没有左节点,那么就左节点深度变量就是1,有左节点的话,左节点深度变量就是对左节点调用此函数返回的结果加1;对右节点也做同样的操作。 最后比较左节点深度和右节点深度,判断谁比较大,就返回哪个变量。这样就能一层一层地递归获取最大深度了。
代码(Java):
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int maxDepth(TreeNode root) {
if (root != null) {// 有此节点
int rightResult;
int leftResult;
if (root.left != null) {// 有左节点
leftResult = maxDepth(root.left) + 1;
} else {// 无左节点
leftResult = 1;
}
if (root.right != null) {// 有右节点
rightResult = maxDepth(root.right) + 1;
} else {// 无右节点
rightResult = 1;
}
// 判断哪边更深,返回更深的深度
return leftResult > rightResult ? leftResult : rightResult;
} else {// 无此节点,返回0
return 0;
}
}
}
不过我们稍加思考一下,就可以进一步简略一下代码。因为我们代码里对于root为null的情况下返回的是0,那其实没有左节点时,对齐使用函数返回的也会是0,加1的话就是我们需要的1了,所以其实不用判断有无左节点,右节点也是一样。所以可以简化如下:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int maxDepth(TreeNode root) {
if (root != null) {
int rightResult = maxDepth(root.left) + 1;
int leftResult = maxDepth(root.right) + 1;
return leftResult > rightResult ? leftResult : rightResult;
} else {
return 0;
}
}
}
也可以额外写个函数,在参数里传递深度。
// C++:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int depth(TreeNode* node, int level) {
if (node == NULL) return level-1;
int left = depth(node->left, level+1);
int right = depth(node->right, level+1);
return max(left, right);
}
int maxDepth(TreeNode* root) {
return depth(root, 1);
}
};
相关文章
- 10个2017的预测:数据科学、机器学习和物联网
- 交易无处不在,拿什么来守护支付安全?
- 大数据分析激活电力价值,八大案例深度解析电力大数据应用
- 大数据时代激活数据管理新思路
- 玩转Docker,必须要遵守这8条安全准则!
- 2017年值得关注的数据中心趋势预测
- 物联网策略与设计“七宗罪”
- 亚马逊前首席科学家:大数据价值体现在AI、BI、CI、DI
- 医疗健康大数据服务平台技术架构
- 2016年全球关于大数据分析领域的大事记
- 2017年大数据发展十大新趋势
- 选择数据中心托管的几大益处
- 阿里、万国、XDC+ 数据中心建设经验分享
- 为什么说传统分布式事务不再适用于微服务架构?
- 为何企业无法从数据科学中真正获得价值?
- 数据中心市场竞争的四大利器
- Synergy Research:目前全球大型数据中心数量已超过300个
- 如何用Kano模型量化用户需求?
- 数据中心虚拟化驱动全球数据中心架构市场
- 为何企业无法从数据科学中真正获得价值?