找出二叉树两节点的最低公共祖先节点

题目:给定两个二叉树的节点node1和node2,找到它们的最低公共祖先节点

o1和o2的所有结构关系分为两类:

1、o1是o2的最低公共祖先,或o2是o1的最低公共祖先

2、o1与o2不互为最低公共祖先,最低公共祖先是通过往上汇聚寻找的

//返回两节点的最低公共祖先节点
    public static Node lowestAncestor(Node head, Node o1, Node o2) {
        if (head == null || head == o1 || head == o2) {
            return head;
        }
        Node left = lowestAncestor(head.left, o1, o2);
        Node right = lowestAncestor(head.right, o1, o2);
        //左右两棵树,都有返回值(情况1不会遇到)
        //head是最初的汇聚点,head会一直往上扔
        if (left != null && right != null) {
            return head;
        }
        //左右两棵树,并不都有返回值
        return left != null ? left : right;
    }    

解读

找出二叉树两节点的最低公共祖先节点

 

上一篇:Lambda表达式与方法引用


下一篇:项目开发规范