学习算法,锻炼自我!记录自己的成长过程!
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
这道题的解法有点不好想,先逐行解释一下
var lowestCommonAncestor = function (root, p, q) {
//2.找到p,q节点直接返回p,q节点
//或者当遍历到 null 节点,空树不存在 p 和 q
if (!root || root === p || root === q) {
return root;
};
//1.先从这里看
//首先我们以当前节点root为头,向下找看是否能找到p,q节点
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
//3.如果以当前节点为头,找到了p,q节点,则当前节点为最近公共祖先
if (left && right) {
return root;
};
//4.如果只存在其中一个比如只有左子节点
//说明p,q节点都在左子节点上
return left ? left : right;
};