- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
递归 dfs
- 一棵二叉树的直径长度是任意两个结点路径长度中的最大值
- 这条路径可能穿过也可能不穿过根结点
两个公式：
- 最长路径 = 左子树最长路径 + 右子树最长路径 + 1 (根结点)
- 高度(最大深度) = 左右子树中的最大深度 + 1 (根结点)
constdiameterOfBinaryTree=function(root){letans=1functiondepth(node){if(node===null)return0letL=depth(node.left)letR=depth(node.right)ans=Math.max(ans,L+R+1)returnMath.max(L,R)+1}depth(root)returnans-1}
- 时间复杂度: O(n)
- 空间复杂度: O(H)，H 为二叉树的高度