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

直接搜索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;
    }
}
9

要想找到两个节点的最近公共祖先节点,我们可以从两个节点往上找,每个节点都往上走,一直走到根节点,那么根节点到这两个节点的连线肯定有相交的地方,如果是从上往下走,那么最后一次相交的节点就是他们的最近公共祖先节点。我们就以找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主页查看更多的详细题解

10

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

/**
 * 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 null;
        }
        Stack<TreeNode> stack = new Stack<>();
//        1  定义一个方法传入一棵树,然后查找对应的节点,开始用bfs,后面用dfs
        ArrayDeque<TreeNode> objects = new ArrayDeque<>();
        objects.offer(root);
        while(!objects.isEmpty()){
            TreeNode poll = objects.poll();
            boolean grandParent = findGrandParent(poll, p, q);
            if(grandParent){
                stack.push(poll);
            }
            if(poll.left!=null){
                objects.offer(poll.left);
            }
            if(poll.right!=null){
                objects.offer(poll.right);
            }
        }
//        2 在同一棵树同时查找两个节点,如果都能够找到的话,那么这个树的根节点就是他们的祖先节点
//        3然后依次的遍历每一个节点构成的子树,把他们的根节点压入栈中,如果最后栈中有数据那么取第一个就是他们最近的祖先节点,如果没有数据那么就没有
        if(!stack.isEmpty()){
            return stack.pop();
        }
        return null;
    }

    private boolean findGrandParent(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stack = new Stack<>();
        int count=0;
        if(root==null){
            return false;
        }
        while(root!=null||!stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
            if(!stack.isEmpty()){
                root=stack.pop();
//                如果两个都在这个节点的时候就可以加count
                if(root.val==p.val||root.val==q.val){
                    count++;
                }
                root=root.right;
            }
        }
        return count==2;
    }
}

b1968c854eeda47e228afc58af1d511.png

1

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

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
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个有结果,在同一子树上,返回即可

1

if(left==null&&right==null)return null;

这个判断是多余的, 在return语句中已经包括了

if(root.val==p.val||root.val==q.val){
                    count++;
                    if(count==2){
                        return true;
                    }
                }

在count==2的时候直接返回就可以达到要求了,小菜鸡简单易操作解法
8488a5de3dd700de8bc2c8fe6d44260.png

老哥顶

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