二叉树公共祖先问题

package dayone.tre;

/***
 * o1和o2为head二叉树中的点，找出o1和02的最近公共祖先
 */
public class Test {

    public static Node lowestAncestor(Node head, Node o1, Node o2) {
        //情况一：o1为o2的祖先节点或o2为o1的祖先节点时，则head即为最近公共祖先
        if (head == null || head == o1 || head == o2) {
            return head;
        }
        //情况二
        //向左树递归寻找数据
        Node left = lowestAncestor(head.left, o1, o2);
        //向右树递归寻找数据
        Node right = lowestAncestor(head.right, o1, o2);
        //当左子树和右子数都不为空时，head即为最近公共祖先
        if (left != null && right != null) {
            return head;
        }
        //左右两棵树，并不都有返回值
        return left != null ? left : right;
    }

}

class Node {
    public int value;

    public Node left;

    public Node right;

    public Node(int data) {
        this.value = data;
    }
}

该问题为二叉树dp问题，可以分为两种情况进行求解：

　　1.o1为o2的祖先节点或o2为o1的祖先节点

　　2.祖先为o1和o2外的节点