深度优先遍历 DFS
解题思路
求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式；
在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的 left 和 right）做逻辑判断；
3=4. p、q 出现的位置可能会有以下两种情况
要理解如果返回值 left 为空，right 不为空为什么要返回 right，为什么可以用返回 right 传给上一层结果；
图解
复杂度
-
时间复杂度
O(N)： 其中 N 为二叉树节点数，最差情况下，需要递归遍历树的所有节点； -
空间复杂度
O(N)： 最差情况下，递归深度达到 N 则二叉树退化成了链表，系统使用O(N)大小的额外空间；
代码实现
var lowestCommonAncestor = function (root, p, q) {
if (root === null) return root;
// 寻找 p、q，找到则立刻返回告诉上层节点，找到了
if (root === p || root === q) return root;
// 自顶向下检查 p、q 能否在左、右子树中找到（相当于前序遍历寻找 p、q）
let leftNode = lowestCommonAncestor(root.left, p, q);
let rightNode = lowestCommonAncestor(root.right, p, q);
// 自底向上，返回公共祖先
// - p、q 都在 右子树中，返回 递归右子树 的结果
if (leftNode === null && rightNode !== null) return rightNode;
// - p、q 都在 左子树中，返回 递左子树 的结果
else if (rightNode === null && leftNode !== null) return leftNode;
// - p、q 没有找到，返回 null
else if (leftNode === null && rightNode === null) return null;
// - p、q 在 左右子树中，直接返回 root 公共祖先
return root;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 316. 去除重复字母
上一篇
评论
