亲宝软件园·资讯

展开

Java 二叉树最近公共祖先

Scintillator. / 人气:0

思路一:先假设这棵树是二叉搜索树

首先我们补充说明一下什么是二叉搜索树:

在二叉搜索树中,对于每一个节点来说,他的左子树中的值都比他小,右子树的中的值都比他大。所以二叉搜索树的中序遍历是一组有序的数据。

在这里插入图片描述

对于上述这棵树,假设要求 p q 的最近公共祖先。

那么它有以下情况:

在这里插入图片描述

在这里插入图片描述

对于普通的二叉树来说,也无非就这几种情况:pq都在左,pq都在右,pq一左一右,pq有一个是根节点。

所以分别递归的去左子树和右子树中找 p q 节点的公共祖先,找到了则返回该节点,没有找到则返回空。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

根据上述思路,我们很容易写出代码

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

    // p 为当前树的根节点
    if(p == root) return p;
    // q 为当前树的根节点
    if(q == root) return q;
    
    // 去左子树中找
    TreeNode left = lowestCommonAncestor(root.left,p,q);
    // 去右子树中找
    TreeNode right = lowestCommonAncestor(root.right,p,q);

    // 左边右边都找到了
    if(left != null && right != null) {
        return root;
    }
    // 左边找到了,右边没找到
    if(left != null) {
        return left;
    }
    if(right != null) {
        return right;
    }
    return null;
}

思路二:假设该树是用孩子双亲表示法

每个节点会保存它父亲节点的地址,可以层层网上找,直到找到两链表的第一个交点,该交点就是他们的公共祖先。

而对于普通的二叉树来说,只能层层往下找,不能往上,所以要保留两节点的路径,直到两路径的最后一个相同节点。这里我们用栈来保留两个节点的路径。

在这里插入图片描述

先弹出元素多的栈中的元素,然后两个栈再一起弹出,直到要弹出的节点相等,就是其最近公共祖先。

在这里插入图片描述

那么这里最大的难点就是存储路径。

这里用栈来存储路径,当遍历到一个节点时,将该节点放入栈中,再递归该节点的左树和右树找,如果找到了则保留路径,没找到则弹出。

假设找下图的p:

在这里插入图片描述

先将根节点放入栈,递归root节点的左子树找,找不到则弹出,在右子树中找。

在这里插入图片描述

当 root 走到 6 的时候,发现该节点的左右均为空,说明在该子树中没找到目标节点,弹出 6 ,在 5 的右子树中继续找。

在这里插入图片描述

同理在 5 的右子树中也找不到,会弹出直到去 3 的右子树找,来到 1 ,找到。

在这里插入图片描述

// 用于找节点的路径
public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
    if(root == null || node == null) {
        return false;
    }
    // 将当前节点放入栈中
    stack.push(root);
    
    if(root.val == node.val) {
        return true;// 找到了
    }
    // 当前节点没找到,去左子树找
    boolean flag = getPath(root.left,node,stack);
    // 左子树中找到了,直接返回
    if(flag) {
        return true;
    }
    // 左子树没找到,去右子树找
    flag = getPath(root.right,node,stack);
    // 右子树中找到了,直接返回
    if(flag) {
        return true;
    }
    
    // 左右子树都没找到,弹出节点
    stack.pop();
    return false;

}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root == null) {
        return null;
    }
    Stack<TreeNode> stackp = new Stack<>();
    Stack<TreeNode> stackq = new Stack<>();

    // 分别得到  p q 的路径
    getPath(root,p,stackp);
    getPath(root,q,stackq);

    int sizep = stackp.size();
    int sizeq = stackq.size();

    if(sizep > sizeq) {
        int size = sizep - sizeq;
        // 弹出元素直至两栈中元素个数相等
        while(size > 0) {
            stackp.pop();
            size--;
        }
    }else {
        int size = sizeq - sizep;
        // 弹出元素直至两栈中元素个数相等
        while(size > 0) {
            stackq.pop();
            size--;
        }
    }

    // 一起弹出,直到找到第一个相同的元素
    while(!stackp.isEmpty() && !stackq.isEmpty()) {
        if(stackp.peek() == stackq.peek()) {
        	// 找到了,就返回该节点
            return stackq.pop();
        }else {
            stackp.pop();
            stackq.pop();
        }
    }
    // 没找到,返回 null
    return null;
}

加载全部内容

相关教程
猜你喜欢
用户评论