二叉树两个节点的最近公共祖先问题
二叉树两个节点的最近公共祖先问题
作者：Grey
原文地址：
题目描述
给定一棵二叉树的头节点 head，和另外两个节点 a 和 b , 返回 a 和 b 的最低公共祖先。
题目链接见：LeetCode 236. Lowest Common Ancestor of a Binary Tree
主要思路：
本题也是利用二叉树的递归套路来解。
定义好 Info 信息
public static class Info {
public Info(boolean findA, boolean findB, TreeNode ancestor) {
this.findA = findA;
this.findB = findB;
this.ancestor = ancestor;
}
private boolean findA;
private boolean findB;
private TreeNode ancestor;
}
其中
findA表示能否在当前(子)树下找到 a 节点；
findB表示能否在当前(子)树下找到 b 节点；
ancestor表示当前两个节点的最低公共祖先是什么。
首先考虑一些边界条件，例如
if (a == null) {
// a 为 null，不管 b 是否为 null，公共祖先都是 b
return b;
}
if (b == null) {
// b 为 null， 不管 a 是否为 null，公共祖先都是 a
return a;
}
定义递归函数
Info p(TreeNode head, TreeNode a, TreeNode b)
递归含义是：以 head 为头的树，a 和 b 的公共祖先是什么，封装成 Info 返回。
接下来看递归函数的主要逻辑
首先是 base case，如果 head 为 null，则 findA = false，findB = false，a 和 b 的公共祖先也是 null
即
if (head == null) {
return new Info(false, false, null);
}
分析了 base case，接下来是普遍情况，如果 head 不为 null，则去左树收集信息，去右树也收集信息，然后把左右两树的信息整合成 head 的信息返回
即
// 左树收集信息
Info leftInfo = p(head.left, a, b);
// 右树收集信息
Info rightInfo = p(head.right, a, b);
// 整合
......
最后，我们需要把左右两树返回的信息进行整合，首先，以 head 为头的树，findA的取值取决于如下三种情况：
情况1，左树包含 a，即 leftInfo.findA
情况2，右树包含 a，即 rightInfo.findA
情况3，head 就是 a
三个情况有一个满足，以 head 为头的树 findA = true，
findB类似，
即下述代码所表达的含义
// 这
boolean findA = leftInfo.findA || rightInfo.findA || head == a;
boolean findB = leftInfo.findB || rightInfo.findB || head == b;
接下来看两个节点的最低公共祖先，首先，如果左树上找到 a 和 b，那么 leftInfo.ancestor 就是 a 和 b 的最低公共祖先；
如果右树上找到 a 和 b，那么 rightInfo.ancestor 就是 a 和 b 的最低公共祖先；
如果左右树一边找到一个，则 head 就是 a 和 b 的最低公共祖先；
如果 a 和 b 在树上都找不到，即findA = false, findB = false，那么 a 和 b 的最低公共祖先就是 null。
即下述代码逻辑
if (findA && findB) {
if (leftInfo.findA && leftInfo.findB) {
return new Info(true, true, leftInfo.ancestor);
} else if (rightInfo.findA && rightInfo.findB) {
return new Info(true, true, rightInfo.ancestor);
}
return new Info(true, true, head);
}
return new Info(findA, findB, null);
完整代码见
class Solution {
public static TreeNode lowestCommonAncestor(TreeNode head, TreeNode a, TreeNode b) {
if (a == null) {
return b;
}
if (b == null) {
return a;
}
// o1和o2都不为null
return p(head, a, b).ancestor;
}
public static Info p(TreeNode head, TreeNode a, TreeNode b) {
if (head == null) {
return new Info(false, false, null);
}
Info leftInfo = p(head.left, a, b);
Info rightInfo = p(head.right, a, b);
boolean findA = leftInfo.findA || rightInfo.findA || head == a;
boolean findB = leftInfo.findB || rightInfo.findB || head == b;
if (findA && findB) {
if (leftInfo.findA && leftInfo.findB) {
return new Info(true, true, leftInfo.ancestor);
} else if (rightInfo.findA && rightInfo.findB) {
return new Info(true, true, rightInfo.ancestor);
}
return new Info(true, true, head);
}
return new Info(findA, findB, null);
}
public static class Info {
public Info(boolean findA, boolean findB, TreeNode ancestor) {
this.findA = findA;
this.findB = findB;
this.ancestor = ancestor;
}
private boolean findA;
private boolean findB;
private TreeNode ancestor;
}
}
时间复杂度为O(N)（即一次后序遍历的时间复杂度）
