236. 二叉树的最近公共祖先

学习算法,锻炼自我!记录自己的成长过程!

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

这道题的解法有点不好想,先逐行解释一下

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;
};
上一篇:关于.NET参数传递方式的思考


下一篇:使用NUnit为游戏项目编写高质量单元测试的思考