美文网首页
二叉树:找出两个节点的最近公共祖先

二叉树:找出两个节点的最近公共祖先

作者: Djbfifjd | 来源:发表于2020-10-12 20:32 被阅读0次

给定二叉树(不是二叉搜索树)和两个节点 n1 和 n2,编程实现找到二者的最近公共祖先(Lowest Common Ancestor,LCA)。

LCA定义:最近公共祖先是两个节点所有公共祖先中离根节点最远的节点。从根开始遍历树,如果任一给定节点(n1和n2)与根匹配,则根为 LCA。如果根与任何节点都不匹配,重复左右子树中寻找节点 n1 和 n2。如果在其左子树中存在一个节点而在右子树中存在的另一个节点,则此节点即为 LCA。如果两个节点都位于左子树中,则 LCA 也位于左子树中,否则 LCA 位于右子树中。由此,找到该树中两个指定节点的最近公共祖先,有三种情况,如图:

为了确定树中节点之间距离:从 n1 节点到 n2 节点的距离,可以计算从根到 n1 的距离加上从根到 n2 的距离,减去从根到它们最近共同祖先的距离的两倍。
import java.util.*;
import java.util.Queue;
//下面使用的遍历方法均为前序遍历
class Node{
    public char val;
    public Node left;//左孩子
    public Node right;//右孩子
    public Node(char val){
        this.val=val;
    }
}
public class BinaryTree {
    // 1、构造二叉树
    public Node buildTree(){
        Node A=new Node('A');
        Node B=new Node('B');
        Node C=new Node('C');
        Node D=new Node('D');
        Node E=new Node('E');
        Node F=new Node('F');
        Node G=new Node('G');
        Node H=new Node('H');
        A.left=B;A.right=C;B.left=D;B.right=E;//这里是构造二叉树的关键
        C.left=F;C.right=G;E.right=H;
        return A;
    }
    //找两个结点最近的公共祖先
    public Node lowstCommonAncestor(Node root,Node p,Node q){
        if(root==null){
            return null;
        }
        if(root==p||root==q){
            return root;
        }
        Node left=lowstCommonAncestor(root.left,p,q);
        Node right=lowstCommonAncestor(root.right,p,q);
        if(left!=null&&right!=null){
            return root;
        }else if(left!=null){
            return left;
        }else{
            return right;
        }
    }
    public static void main(String[] args) {
        BinaryTree binaryTree=new BinaryTree();
        Node root=binaryTree.buildTree();

        System.out.println("找两个结点最近的公共祖先:"+binaryTree.lowstCommonAncestor(root,root.left,root.right.left));//这里打印出的是地址,可推理该公共祖先是A
        System.out.println(root);//这个是根即A的地址,两者比较会发现是一致的
    }
}

相关文章

  • 最近公共祖先系列

    最近公共祖先I 描述: 给定一棵二叉树,找到两个节点的最近公共父节点 (LCA)。最近公共祖先是两个节点的公共的祖...

  • 二叉树-最近的公共祖先

    已知二叉树,求二叉树中给定的两个节点的最近公共祖先。 最近公共祖先: 两节点v与w的最近公共祖先u,满足在树上最低...

  • lintcode 最近公共祖先

    给定一棵二叉树,找到两个节点的最近公共父节点(LCA)。最近公共祖先是两个节点的公共的祖先节点且具有最大深度。样例...

  • 小米-基础算法-最近公共祖先

    给一棵二叉树和二叉树中的两个节点,找到这两个节点的最近公共祖先LCA。两个节点的最近公共祖先,是指两个节点的所有父...

  • 算法—— 最近公共祖先 III

    给一棵二叉树和二叉树中的两个节点,找到这两个节点的最近公共祖先LCA。两个节点的最近公共祖先,是指两个节点的所有父...

  • LintCode 578. 最近公共祖先 III

    题目描述 给一棵二叉树和二叉树中的两个节点,找到这两个节点的最近公共祖先LCA。 两个节点的最近公共祖先,是指两个...

  • LeeteCode 236.二叉树的最近公共祖先(Lowest

    二叉树的最近公共祖先 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“...

  • leetCode进阶算法题+解析(三十一)

    二叉树的最近公共祖先 题目:给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为...

  • [LeetCode]236. 二叉树的最近公共祖先

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

  • 【算法】二叉树的最近公共祖先

    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 最近公共祖先的定义为:“对于有根树 T 的两个节点 p、...

网友评论

      本文标题:二叉树:找出两个节点的最近公共祖先

      本文链接:https://www.haomeiwen.com/subject/dzpppktx.html