給一棵二叉樹(shù)和二叉樹(shù)中的兩個(gè)節(jié)點(diǎn)域滥，找到這兩個(gè)節(jié)點(diǎn)的最近公共祖先 LCA纵柿。兩個(gè)節(jié)點(diǎn)的最近公共祖先，是指兩個(gè)節(jié)點(diǎn)的所有父親節(jié)點(diǎn)中（包括這兩個(gè)節(jié)點(diǎn)）启绰，離這兩個(gè)節(jié)點(diǎn)最近的公共的節(jié)點(diǎn)昂儒。每個(gè)節(jié)點(diǎn)除了左右兒子指針以外，還包含一個(gè)父親指針parent委可，指向自己的父親渊跋。
樣例
對(duì)于下面的這棵二叉樹(shù)
4
/ \
3 7
/ \
5 6
LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
代碼
/**
* Definition of ParentTreeNode:
*
* class ParentTreeNode {
* public ParentTreeNode parent, left, right;
* }
*/
public class Solution {
/**
* @param root: The root of the tree
* @param A, B: Two node in the tree
* @return: The lowest common ancestor of A and B
*/
public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root,
ParentTreeNode A,
ParentTreeNode B) {
// 用數(shù)組分別存儲(chǔ) A , B 結(jié)點(diǎn)向上尋找的結(jié)點(diǎn)
ArrayList<ParentTreeNode> pathA = getPath2Root(A);
ArrayList<ParentTreeNode> pathB = getPath2Root(B);
// 忘記 -1 會(huì)出現(xiàn)數(shù)組下標(biāo)越界
int indexA = pathA.size() - 1;
int indexB = pathB.size() - 1;
ParentTreeNode lowestAncestor = null;
// 從最遠(yuǎn)的公共祖先開(kāi)始尋找，找到最近的公共祖先
while (indexA >= 0 && indexB >= 0) {
// break 時(shí)不需要更新 lowestAncestor撤缴，
// 其上一個(gè) pathA.get(indexA) == pathB.get(indexB) 的 lowestAncestor 是所需的
if (pathA.get(indexA) != pathB.get(indexB)) {
break;
}
lowestAncestor = pathA.get(indexA);
indexA--;
indexB--;
}
return lowestAncestor;
}
private ArrayList<ParentTreeNode> getPath2Root(ParentTreeNode node) {
ArrayList<ParentTreeNode> path = new ArrayList<>();
while (node != null) {
path.add(node);
node = node.parent;
}
return path;
}
