leetcode 236.二叉树的最近公共祖先

思路一：作者的思路是按照数据结构中学的那样，按照层序遍历的遍历顺序给结点编号，然后每个结点的编号/2就是它的祖先节点，一直往上推，然后将其存储起来，然后在其中找到深度最深并且公有的那个结点就是最近的公共节点。

这个方法放在数据量小的时候是可行的，但是数据量过大，就会时间超时，并且会浪费特别多空间，所以慎重取用。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null||q==null||p==null)return null;Map<Integer,TreeNode>m_cnt=new HashMap<>();Map<TreeNode,Integer>m_Node=new HashMap<>();int cnt=0;Deque<TreeNode>q1=new LinkedList<>();q1.addLast(root);while(cnt<=100000){TreeNode tmp=q1.getFirst();if(tmp!=null){if(tmp.left!=null)q1.addLast(tmp.left);else if(tmp.left==null)q1.addLast(null);if(tmp.right!=null)q1.addLast(tmp.right);else if(tmp.right==null)q1.addLast(null);}else{q1.addLast(null);q1.addLast(null);}q1.removeFirst();cnt++;m_cnt.put(cnt,tmp);m_Node.put(tmp,cnt);}List<TreeNode>list1=new ArrayList<>();List<TreeNode>list2=new ArrayList<>();int p_cnt=m_Node.get(p);int q_cnt=m_Node.get(q);for(int i=p_cnt;i>0;i/=2){if(m_cnt.get(i)!=null){list1.add(m_cnt.get(i));}}for(int i=q_cnt;i>0;i/=2){if(m_cnt.get(i)!=null){list2.add(m_cnt.get(i));}}if(list1.size()>list2.size()){for(int i=0;i<list1.size();i++){TreeNode t=list1.get(i);if(list2.indexOf(t)>=0){return t;}}}else{for(int i=0;i<list2.size();i++){TreeNode t=list2.get(i);if(list1.indexOf(t)>=0){return t;}}}return null;}
}

思路二：递归。

这个题的递归其实挺难想的，但是大体思路很明确。因为这个递归的过程使用并不与它的真实含义一致。所以我们在递归的时候就会感觉很奇怪。

思路是这样的：我们首先需要知道给出的两个结点在哪。是在当前根节点的左子树还是右子树。如果是分别在两侧，那么当前的根节点就是他们的公共祖先。

如果它们在一侧，我们就对一侧进行递归。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root==null||q==root||p==root)return root;TreeNode l=lowestCommonAncestor(root.left,p,q);TreeNode r=lowestCommonAncestor(root.right,p,q);if(l==null)return r;if(r==null)return l;if(l==null&&r==null)return null;return root;}
}