二叉樹兩個節點的最近公共祖先問題
二叉樹兩個節點的最近公共祖先問題
作者：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)（即一次後序遍歷的時間複雜度）
