- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
DFS 深度优先搜索
树的深度 = 左右子树的最大深度 + 1
constmaxDepth=function(root){if(!root){// 递归终止条件return0}else{constleft=maxDepth(root.left)constright=maxDepth(root.right)returnMath.max(left,right)+1}};
- 时间复杂度: O(n)
- 最坏空间复杂度: O(height), height 表示二叉树的高度
BFS 广度优先搜索
层序遍历时记录树的深度。
二叉树的层序遍历可参考轻松拿下二叉树的层序遍历
constmaxDepth=function(root){letdepth=0if(root===null){returndepth}constqueue=[root]while(queue.length){letlen=queue.lengthwhile(len--){constcur=queue.shift()cur.left&&queue.push(cur.left)cur.right&&queue.push(cur.right)}depth++}returndepth};
- 时间复杂度: O(n)
- 空间复杂度: O(n)