Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.According to 
the [definition of LCA on Wikipedia](https://en.wikipedia.org/wiki/Lowest_common_ancestor): “The lowest 
common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as 
descendants (where we allow a node to be a descendant of itself)., since a node can be a descendant of 
itself according to the LCA definition.

题目：求两个节点的最低公共祖先
思路：遍历出根到指定节点的路径，转化为求链表第一个不相等的节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || p == null || q == null)
            return null;
        List<TreeNode> st1 = new LinkedList<TreeNode>();
        List<TreeNode> st2 = new LinkedList<TreeNode>();
        st1.add(root);
        st2.add(root);
        travel(root, st1, p);
        travel(root, st2, q);
        TreeNode ans = null;
        for(int i=0; i<st1.size() && i< st2.size(); i++){
            if(st1.get(i) == st2.get(i)){
                ans = st1.get(i);
            }else{
                break;
            }
        }
        return ans;

    }

    public boolean travel(TreeNode root, List<TreeNode> st, TreeNode q){
        if(root == q){
            return true;
        }
        if(root.left != null){
            st.add(root.left);
            if(travel(root.left, st, q)) return true;
            st.remove(st.size()-1);
        }
       
        if(root.right != null){
            st.add(root.right);
            if(travel(root.right, st, q)) return true;
            st.remove(st.size()-1);
        }
        return false;
    }

}