[JAVA]寻找最低公共祖宗结点

题目来源：leetcode

题目描述：

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: “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 = 1
Output: 3
Explanation: 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         //bfs
13         if(p.left==q||p.right==q) return p;
14         if(q.left==p||q.right==p) return q;
15         Stack<TreeNode> s1=new Stack();
16         Stack<TreeNode> 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     // }空间受限

View Code

加油啊

原创供学习参考使用，转载请注明出处http://www.cnblogs.com/cuphoria/ @jm_epiphany