題目：
例如烟阐，給定如下二叉樹: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出: 3
解釋: 節(jié)點(diǎn) 5 和節(jié)點(diǎn) 1 的最近公共祖先是節(jié)點(diǎn) 3苗胀。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
思想：
分別找到root到p,q的路徑，返回路徑中最后一個(gè)相同的節(jié)點(diǎn)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.util.LinkedList;
import java.util.ArrayList;
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(p==null) {
return q;
}
if(q==null) {
return p;
}
ArrayList<TreeNode> res1 = new ArrayList<>();
getPath(root,p, new LinkedList<>(),res1);
ArrayList<TreeNode> res2 = new ArrayList<>();
getPath(root,q, new LinkedList<>(),res2);
TreeNode node = null;
int i = 0;
while(i<res1.size()&&i<res2.size()) {
if(res1.get(i)==res2.get(i)) {
node = res1.get(i);
i++;
}else{
break;
}
}
return node;
}
private void getPath(TreeNode root, TreeNode node, LinkedList<TreeNode> temp, ArrayList<TreeNode> res) {
if(root==null) {
return;
}
temp.add(root);
if(root==node) {
for(int i=0;i<temp.size();i++) {
res.add(temp.get(i));
}
return;
}
getPath(root.left,node,temp,res);
getPath(root.right,node,temp,res);
temp.pollLast();
}
}
