题目:给定两个二叉树的节点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; }
解读