235. 二叉搜索树的最近公共祖先

题解：
思路一：
  • 我们使用 HashMap 来存储，子节点的值 -> 父节点。
  • dfs二叉树，构建map，保存每个节点对应的父节点
  • 根据map，分别获得传入两个节点的祖先节点数组
  • 查询这两个祖先节点数组的最近的公共元素
    • 将一个数组转为set
    • 从 0开始遍历第二个数组，找到第一个set中也包含的，就是最终结果。

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

// 保存 <值 ， 父节点>
    HashMap<Integer, TreeNode> hashMap;

    public void dfs(TreeNode node ,TreeNode parent){
        if (node == null) return;

        hashMap.put(node.val,parent);

        dfs(node.left,node);
        dfs(node.right,node);
    }

    public List getParents(TreeNode node){

        List<TreeNode> plist = new LinkedList<>();

        TreeNode pnode = node;
        while (pnode != null){
            plist.add(pnode);
            pnode = hashMap.get(pnode.val);
        }

        return plist;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) return null;

        hashMap = new HashMap<>();

        // 处理 父节点 字典
        dfs(root,null);

        // p 的所有父节点
        List<TreeNode> plist = getParents(p);

        // q 的所有父节点
        List<TreeNode> qlist = getParents(q);

        HashSet set = new HashSet(plist);

        for (int i = 0; i < qlist.size(); i++) {
            if (set.contains(qlist.get(i)))
                return qlist.get(i);
        }

        return null;
    }

时间复杂度 ： O(N)

空间复杂度 ； O(N)

image-20200511114838745

优化：
思路二：

上述解题过程中， 发现我们完全没有用到 二叉搜索树 特殊的性质，时间复杂度比较高，由上图可以看出，虽然算法通过，但是执行效率非常差。 接下来，我们尝试优化。

image-20200511115321556

  • 发现二叉搜索树的最近公共祖先节点，总是在传入两个节点值之间(比如，上图中0, 4的最近公共祖先是 2。 4和7的最近公共祖先是6。)
  • 当root.val 比两者都大时，则在左子树中查找
  • 当root.val 比两者都小时，则在右子树中查找
  • 否则，在两者之间，就是最近公共祖先节点

递归:

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) return null;

        if (root.val > q.val && root.val > p.val){

            return lowestCommonAncestor(root.left,p,q);
        }else if (root.val < q.val && root.val < p.val){
            return lowestCommonAncestor(root.right,p,q);
        }

        return root;
    }

思路三：

迭代

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) return null;

        while (root != null) {
            if (root.val > q.val && root.val > p.val) {
                root = root.left;
            } else if (root.val < q.val && root.val < q.val) {
                root = root.right;
            } else {
                return root;
            }
        }
        return null;
    }