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

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5

1.一刷

1. 一开始的想法是通过二叉树顺序存储的下标找到最近公共祖先。分为两个操作，首先需要遍历整个二叉树找到p和q对应的索引下标，再根据pnum=(pnum-1)/2得到父节点索引下标，直至pnum=qnum就得到最近的公共祖先的索引下标。但是不知道是我写的有问题，还是题目给的一个例子有问题(感觉是用例bug)，[-1,0,null,1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null...]这个用例没能通过。(这用例给的是棵什么鬼树？？？还是说它想表达的是一颗链状树？)。总之要点在于：

• left=pnum*2+1; right=pnum*2+2; parent=(pnum-1)/2

2. 另一种思路是用哈希表记录当前节点值和父节点的关系HashMap<Integer p.val,TreeNode p.parent >；再用一个队列存放p的父节点，别忘记要先把p自身放入队列中。当list.contains(hashmap.get(q.val))时则找到最近公共祖先。

3. 最优的方法是后序遍历。后序遍历的特点是先递归后处理，天然的自底向上二叉树回溯，最先处理的一定是叶子节点，写法如下：

   • 确定终止退出条件
   • 递归调用
   • 处理节点

   当一发现一个节点左子树有p,右子树有q节点，那么这个节点就是最近的公共祖先，因为后序遍历是从底向上找，所以找到的一定是最深的。难点的在于当左子树和右子树一边找到p另一边什么都没找到返回null时，这时候函数直接返回找到的p或者q节点，这个节点依旧具有深度最深的特性。

   public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
               if(root==null)
               return null;
               if(root==p||root==q)
               return root;
               TreeNode left=lowestCommonAncestor(root.left,p,q);
               TreeNode right=lowestCommonAncestor(root.right,p,q);
               if(left!=null&&right!=null)
               return root;
               if(left==null&&right==null)
               return null;
               return (right!=null)?right:left;
   
       }
   

2.二刷

分析：如果以当前节点为根的子树，包含p节点或者q节点，则返回true。

那么最近公共祖先节点无非就以下两种情况：

• 左子树为true，同时右子树为true
• 左子树或者右子树存在一个true，然后当前root节点为pq其中一个节点。

class Solution {
      TreeNode res;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root,p,q);
        return res;
    }
    public boolean dfs(TreeNode root, TreeNode p, TreeNode q){
        boolean left=root.left==null?false:dfs(root.left,p,q);
        boolean right=root.right==null?false:dfs(root.right,p,q);
        if(left&&right){
            res=root;
            return true;
        }
        if(left||right){
            if(root==q||root==p) res=root;
            return true;
        }
        if(root==q||root==p) return true;
        return false;
    }
}