题目描述

• ac了，但是看了题解发现有更好的做法
  

思路 & 代码

• 对于一个结点rootNode，p、q有这么几种情况：

1. p、q分别在其左右子树中，那么好说，rootNode就是答案
2. p、q都在其右子树中（包括p or q就是rootNode)，那么就以rootNode.right开始进行新的递归
3. p、q都在其左子树中，和2差不多

• 由此，流程：先递归left & right，都不为null的情况就是情况1。其中一方为null的情况就是情况2、3，在递归中返回最终结果。

/**
 * 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) {
        // 叶子结点 & 已经找到 p or q 的情况下返回 root
       if(root == null || root == p || root == q){
           return root;
       } 
       TreeNode right = lowestCommonAncestor(root.right, p, q);
       TreeNode left = lowestCommonAncestor(root.left, p, q);
       // left == null的情况，说明两结点都在root的右侧
       if(left == null){
           return right;
       }
       // 类似上，都在左侧
       if(right == null){
           return left;
       }
       // 否则说明分布在root的左右两侧，那么root就是最近公共父结点。
       return root;
    }
}

• 自己想的方法：用两条链表，按深度存储p、q所有父结点
• 然后建立哈希集，存储q的所有父结点
• 接着用q来查找哈希集中最近的父结点即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

 // ac了，但是效率比较低，O(n * 4) & O(n * 3)，总体来说还是O(n) O(n)的。
 class Solution {
    boolean found;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 提示很重要
        LinkedList<TreeNode> superP = new LinkedList<>();
        LinkedList<TreeNode> superQ = new LinkedList<>();
        findSuper(superP, root, p);
        found = false;
        findSuper(superQ, root, q);
        // 接下来用HashSet来找最近的公共子结点
        Set<TreeNode> hash = new HashSet();
        for(TreeNode temp : superP){
            hash.add(temp);
        } 
        while(true){
            TreeNode temp = superQ.removeLast();
            if(hash.contains(temp)){
                return temp;
            }
        }
    }
    // 包括自己，自己也存入
    void findSuper(LinkedList<TreeNode> superP, TreeNode root, TreeNode target){
        if(root == null){
            return;
        }
        superP.add(root);
        // 找到了，结束寻找。
        if(root == target){
            found = true;
            return;
        }
        // 还没找到，继续找
        findSuper(superP, root.left, target);
        // 判断一下左边递归有没有找到
        if(!found){
            findSuper(superP, root.right, target);
        }
        // 以当前root开始的递归结束，删掉当前父结点
        if(!found){
            superP.removeLast();
        }
    }
}