力扣面试150题--二叉树的最近公共祖先

Day 53

题目描述

思路

初次思路：转化为中序和后序来找祖先，具体见代码。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<TreeNode>hou;
    public List<TreeNode>mid;
    public Map<TreeNode,Integer>midhao;
    public Map<TreeNode,Integer>houhao;
    int i=0;
    int j=0;
    public void houpai(TreeNode root){
        if(root==null){
            return;
        }
        houpai(root.left);
        houpai(root.right);
        hou.add(root);//保存到后序遍历数组中
        houhao.put(root,j);//记录序号
        j++;
    }
     public void midpai(TreeNode root){
        if(root==null){
            return;
        }
        midpai(root.left);
        mid.add(root);//保存在中序遍历数组
        midhao.put(root,i);//记录序号
        i++;
        midpai(root.right);
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
       hou=new ArrayList<TreeNode>();
       mid=new ArrayList<TreeNode>();
       midhao=new HashMap<TreeNode,Integer>();
       houhao=new HashMap<TreeNode,Integer>();
       houpai(root);
       midpai(root);
       int houp,midp;
       int houq,midq;
       houp=houhao.get(p);
       midp=midhao.get(p);//找到p在后序和中序遍历的序号
       houq=houhao.get(q);
       midq=midhao.get(q);//找到q在后序和中序遍历的序号
       i=houhao.get(root);
       j=midhao.get(root);//找到根在后序和中序遍历的序号
       int midbeg,midend,houbeg,houend;
       midbeg=0;//某一子树中序遍历的起点
       midend=mid.size()-1;//某一子树中序遍历的终点
       houbeg=0;//某一子树后序遍历的起点
       houend=hou.size()-1;//某一子树后序遍历的终点
       while(true){
        if((midq<=j&&midp>=j)||(midq>=j&&midp<=j)){//在同一子树就可以输出了
            return mid.get(j);
        }
        else{
            if(midq<j&&midp<j){//都在左子树
              //更新到左子树，排除掉所有的右子树
               midbeg=midbeg;
               int x=midend-j;//右子树的节点数
               midend=j-1;
               houbeg=houbeg;
               houend=houend-x-1;
               root=hou.get(houend);
               j=midhao.get(root);//更新根节点的序号
            }
            else{//都在右子树
                //更新到右子树，排除到所有的左子树
                int x=j-midbeg;//左子树的节点个数
                midbeg=j+1;
                midend=midend;
                houbeg=houbeg+x;
                houend=houend-1;
                root=hou.get(houend);
                j=midhao.get(root);//更新根节点的序号
            }
       }
    }
}
}

题解思路：我们可以用哈希表存储所有节点的父节点，然后我们就可以利用节点的父节点信息从 p 结点开始不断往上跳，并记录已经访问过的节点，再从 q 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是我们要找的最近公共祖先。

class Solution {
    Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
    Set<Integer> visited = new HashSet<Integer>();

    public void dfs(TreeNode root) {//存储到hash表中每个节点的父节点
        if (root.left != null) {
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        if (root.right != null) {
            parent.put(root.right.val, root);
            dfs(root.right);
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        while (p != null) {
            visited.add(p.val);//将p的父节点不断加入到set中
            p = parent.get(p.val);
        }
        while (q != null) {
            if (visited.contains(q.val)) {
            //从q开始向上找父节点，如果找到第一个v存在于p的父节点集合SET说明就找到了二叉树的最近公共祖先
                return q;
            }
            q = parent.get(q.val);//接着找父节点
        }
        return null;
    }
}