題目：
例如，給定如下二叉樹: 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é)點 5 和節(jié)點 1 的最近公共祖先是節(jié)點 3。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree

思想：
分別找到root到p,q的路徑，返回路徑中最后一個相同的節(jié)點

/**
 * 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();
    }
    
}