题目来源：leetcode
题目描述：
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the : “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1Output: 3Explanation: The LCA of nodes 5 and 1 is 3.
一开始就决定了要用深度优先遍历，因为这样会保存他的所有祖宗结点，企图用一个栈去判断，然后发现找俩个最前面那个的前面一个不满足条件（混乱……今天阿里面试还凉了( ╯□╰ )，所以还是两个栈各自保存，他们的祖宗结点路径，也就是先序遍历，然后比较得到最最近一个共同节点。
You are here!
Your runtime beats 100.00 % of java submissions
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 class Solution {11 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {12 //bfs13 if(p.left==q||p.right==q) return p;14 if(q.left==p||q.right==p) return q;15 Stack s1=new Stack();16 Stack s2=new Stack();17 TreeNode visit=root;18 TreeNode r=root;19 while(root!=p)20 {21 if(root==null){22 root=s1.peek();23 if(root.right==null||root.right==visit) { visit=root; s1.pop(); root=null;}24 else{25 visit=root;26 root=root.right;27 }28 29 }30 31 else{32 s1.push(root);33 root=root.left;34 }35 }36 s1.push(root);37 root=r;38 while(root!=q)39 {40 if(root==null){41 root=s2.peek();42 if(root.right==null||root.right==visit) { visit=root; s2.pop(); root=null;}43 else{44 visit=root;45 root=root.right;46 }47 48 } 49 else{50 51 s2.push(root);52 root=root.left;53 }54 }55 s2.push(root);56 root=s1.peek();57 while(s2.search(root)==-1) {58 s1.pop();59 root=s1.peek();60 }61 return root;62 }63 }64 // public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {65 // TreeNode pfather=findFather(root,p);66 // TreeNode qfather=findFather(root,q);67 // if(pfather!=qfather) return lowestCommonAncestor(root,pfather,qfather);68 // return pfather;69 // }70 // public TreeNode findFather(TreeNode root, TreeNode kid)71 // {72 // if(root==null) return null;73 // if(root.left==kid||root.right==kid) return root;74 // TreeNode l=findFather(root.left,kid);75 // TreeNode r=findFather(root.right,kid);76 // return l==null?r:l;77 // }空间受限 加油啊