二叉树的最近公共祖先

题目：
例如，给定如下二叉树: 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
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

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

思想：
分别找到root到p,q的路径，返回路径中最后一个相同的节点

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