- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
递归 dfs
1.从根节点开始遍历，递归左右子树
2.递归终止条件：当前节点为空或者等于 p 或 q，返回当前节点
3.p，q 可能在相同的子树中，也可能在不同的子树中
4.如果左右子树查到节点都不为空，则表示 p 和 q 分别在左右子树中，当前节点就是最近公共祖先
5.如果左右子树中有一个不为空，则返回为空节点
constlowestCommonAncestor=function(root,p,q){if(root===null||root===p||root===q)returnrootletleft=lowestCommonAncestor(root.left,p,q)letright=lowestCommonAncestor(root.right,p,q)if(left!==null&&right!==null){returnroot}returnleft!==null ?left :right}
- 时间复杂度: O(n)
- 空间复杂度: O(n)