讨论/《二叉树》 - 二叉树的最近公共祖先/
《二叉树》 - 二叉树的最近公共祖先
共 12 个回复

要想找到两个节点的最近公共祖先节点,我们可以从两个节点往上找,每个节点都往上走,一直走到根节点,那么根节点到这两个节点的连线肯定有相交的地方,如果是从上往下走,那么最后一次相交的节点就是他们的最近公共祖先节点。我们就以找6和7的最近公共节点来画个图看一下

image.png

我们看到6和7公共祖先有5和3,但最近的是5。我们只要往上找,找到他们第一个相同的公共祖先节点即可,但怎么找到每个节点的父节点呢,我们只需要把每个节点都遍历一遍,然后顺便记录他们的父节点存储在Map中。我们先找到其中的一条路径,比如6→5→3,然后在另一个节点往上找,由于7不在那条路径上,我们找7的父节点是2,2也不在那条路径上,我们接着往上找,2的父节点是5,5在那条路径上,所以5就是他们的最近公共子节点。

其实这里我们可以优化一下,我们没必要遍历所有的结点,我们一层一层的遍历(也就是BFS),只需要这两个节点都遍历到就可以了,比如上面2和8的公共结点,我们只需要遍历到第3层,把2和8都遍历到就行了,没必要再遍历第4层了。

我们来看下代码

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //记录遍历到的每个节点的父节点。
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        parent.put(root, null);//根节点没有父节点,所以为空
        queue.add(root);
        //直到两个节点都找到为止。
        while (!parent.containsKey(p) || !parent.containsKey(q)) {
            //队列是一边进一边出,这里poll方法是出队,
            TreeNode node = queue.poll();
            if (node.left != null) {
                //左子节点不为空,记录下他的父节点
                parent.put(node.left, node);
                //左子节点不为空,把它加入到队列中
                queue.add(node.left);
            }
            //右节点同上
            if (node.right != null) {
                parent.put(node.right, node);
                queue.add(node.right);
            }
        }
        Set<TreeNode> ancestors = new HashSet<>();
        //记录下p和他的祖先节点,从p节点开始一直到根节点。
        while (p != null) {
            ancestors.add(p);
            p = parent.get(p);
        }
        //查看p和他的祖先节点是否包含q节点,如果不包含再看是否包含q的父节点……
        while (!ancestors.contains(q))
            q = parent.get(q);
        return q;
    }


2,递归写法

    public TreeNode lowestCommonAncestor(TreeNode cur, TreeNode p, TreeNode q) {
        if (cur == null || cur == p || cur == q)
            return cur;
        TreeNode left = lowestCommonAncestor(cur.left, p, q);
        TreeNode right = lowestCommonAncestor(cur.right, p, q);
        //如果left为空,说明这两个节点在cur结点的右子树上,我们只需要返回右子树查找的结果即可
        if (left == null)
            return right;
        //同上
        if (right == null)
            return left;
        //如果left和right都不为空,说明这两个节点一个在cur的左子树上一个在cur的右子树上,
        //我们只需要返回cur结点即可。
        return cur;
    }


我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的LeetCode主页查看更多的详细题解

8

直接搜索p,q
如果一个节点两边搜索结果都不为null,那么返回当前节点即可

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==p||root==q||root==null)return root;

        TreeNode left=lowestCommonAncestor(root.left, p, q);
        TreeNode right=lowestCommonAncestor(root.right, p, q);

        if(left==null&&right==null)return null;
        if(left!=null&&right!=null)return root;
        
        return left==null ? right:left;
    }
}
8

不太清楚作者是否是这样考虑的?实在解不出啦,太菜了~ 理解了一遍,试着写了一遍!

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    /**
     * 节点p和节点q只有两种关系:父子关系 兄弟关系
     * 父子关系: 
     *       1.节点p是节点q的子孙节点,即节点p出现在节点q的左或右子树中;返回q即可;
     *       2.节点q是节点p的子孙节点,即节点q出现在节点p的左或右子树中;返回p即可;
     * 兄弟关系:
     *       节点p,q分别出现在某节点的左子树或右子树中;返回该节点即可;
     *
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||root==p||root==q)return root;
        
        TreeNode leftRes=lowestCommonAncestor(root.left,p,q);
        TreeNode rightRes=lowestCommonAncestor(root.right,p,q);
        //p,q在某节点左子树和右子树中
        if(leftRes!=null&&rightRes!=null)return root;
        //左子树和右子树均没有p,q且也不会该节点
        if(leftRes==null&&rightRes==null)return null;
        
        return leftRes==null?rightRes:leftRes;

    }
}
3

老哥顶

这种方法会把同一个节点遍历很多遍

所以分析地那么复杂干啥,我看好多题这些人都分析地很复杂,有必要吗?
本来很好理解的被这些人人为弄复杂了

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL)
        {
            return root;//空的找个屁,既然有那肯定是根
        }
        if(root==p||root==q)
        {
            return root;//既然肯定有,而且有一个就是根,那么直接返回根,
        }
        //如果上面都不是,那么肯定在左右两边
        //根节点往下一层挪,直到根两个中一个相等为止
        TreeNode* left=lowestCommonAncestor(root->left,p,q);
        TreeNode* right=lowestCommonAncestor(root->right,p,q);
        //有三种情况,如果同在左边,那么肯定left不是空,右边为空
        //如果同在右边,那么right不是空,左边为空
        //如果两边都不为空。那么肯定是根节点
        if(left&&right) return root;
        return left? left:right;

    }
};

一句话看你理解不:
1、假设q、p的最近公共祖先是m(m不等于q、p),则q、p的所有祖先都是m的祖先(m也是m的祖先)。由此可知q、p在m的左右子树。q、p同时在其他祖先(除去m)的左或者右子树上。找到一个左右子树分别有q、p的只能是m。因此if(left!=null&&right!=null)return root;
2、假设q、p的最近公共祖先是q或者p。则进行left?left:right以及root==null||root==p||root==q可得到q或者p。

这条语句在搜索过程中只会执行一次,执行这一句的时候意味着当前root就是 --最近-- 公共祖先

不太清楚 if(left!=null&&right!=null)return root; 是什么判断逻辑?假设p、q在左子树跟右子树都存在公共祖先,那为啥p q的公共祖先是root根节点?

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 自顶向下,从root开始,root为空;root为p或者q;root既不是p也不是q,那么转向root的左右子树在其中找p\q
        if not root or root ==p or root==q:
            return root
        l = self.lowestCommonAncestor(root.left, p,q)  # 在左子树中找
        r = self.lowestCommonAncestor(root.right, p,q)  # 在右子树中找
        if l and r:  # 左右子树都有结果,2节点分列两边,返回父root
            return root
        if not l and not r:  # 都没找到返回空
            return None
        return l if l else r  # 只有1个有结果,在同一子树上,返回即可