4
[剑指 Offer 55 - I. 二叉树的深度] | 刷题打卡[5]
source link: https://segmentfault.com/a/1190000039825154
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
一、题目描述：
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7返回它的最大深度 3 。
提示：
节点总数 <= 10000
二、思路分析：
二叉树的深度
二叉树的深度：树中的一个节点的深度是它到根节点的路径上的边的条数。（Robert Sedgewick和Kevin Wayne所著的《算法》第4版）
树中某节点的高度是指从该节点到叶子节点的最长简单路径边的条数。 树的高度等于所有节点的最大深度(即树的深度)。
1. 一棵树只有一个节点或没有节点，它的深度是0；<br/>
2. 二叉树的根节点只有左子树而没有右子树，那么可以判断，二叉树的深度应该是其左子树的深度加1；<br/>
3. 二叉树的根节点只有右子树而没有左子树，那么可以判断，那么二叉树的深度应该是其右树的深度加1；<br/>
4. 二叉树的根节点既有右子树又有左子树，那么可以判断，那么二叉树的深度应该是其左右子树的深度较大值加1。<br/>
三、AC 代码：
var maxDepth = function(root) {
//一个节点都没有
if(root===null){
return 0
}
//只有一个根节点
if(root.left===null && root.right===null){
return 1
}
//递归左子树
let leftMax = maxDepth(root.left)
//递归右子树
let rightMax = maxDepth(root.right)
//返回左右子树的深度较大值加1
return Math.max(leftMax,rightMax)+1
};四、总结：
1.本题考察对二叉树深度的基本理解。什么是树的深度，以及树深度的计算规则和技巧。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK