LCA 类问题

  • LCA 类问题是二叉树的高频问题之一；

  • 有只给 root 的；

  • 还有不给 root 给 parent pointer 的。

  • 想面 FB，最好把各种二叉树问题的 recursion / iteration 还有 root / parent pointer 的写法都练熟才行，只 AC 是不够的。

Lowest Common Ancestor of a Binary Search Tree

  • 递归 ✓

  • 迭代 ✓

  • 复杂度分析 ✓

LCA 问题就是判断给定两个 node {p,q} 与 root 之间的相对位置。在 BST 里这种相对关系看 node.val 就可以。

时间复杂度 O(n)，如果 Tree 的形状是一条线往左或右的 full binary tree 的话。

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Got to check if p and q is null as well;
        if(root == null) return root;

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

        return root;
    }
}

因为是尾递归，显而易见的改法是用 while循环省去递归占用的系统栈空间；

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Got to check if p and q is null as well;
        while(root != null){
            if(root.val > p.val && root.val > q.val) root = root.left;
            else if(root.val < p.val && root.val < q.val) root = root.right;
            else return root;
        }
        return root;
    }
}

Lowest Common Ancestor of a Binary Tree

  • 递归 ✓

  • 迭代 ✓

  • parent指针 todo

  • 复杂度分析 ✓

直接写的暴力解法，知道肯定过不了。。判断子树中 contains 的时间复杂度太高了，而且重复调用很多，完全没优化。

这种解法的时间复杂度是 O(n log n)，因为对于一个 node 来讲，它被 check 的次数等于它和 root 的距离 (也就是 height)。

极少会有 O(n^2) 的 binary tree 算法，因为那意味着每个节点相对于整个树重新计算，而不再是自己从属的路径或者高度。

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

        if(root.val == p.val) return p;
        if(root.val == q.val) return q;

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

        return root;
    }

    private boolean containsNode(TreeNode root, TreeNode node){
        if(root == null) return false;
        if(root.val == node.val) return true;

        return (containsNode(root.left, node) || containsNode(root.right, node));

    }
}

加 containsNode() 函数比较多此一举，其实可以直接用这个函数在 binary tree 上的递归性质去调用自身解决。

函数返回的是 "对于给定 Node 为 root 的 tree 中是否包含 p 或者 q，只要包含一个，就不返回 null 了，而我们相对于当前节点为 root 的结果，就看两边递归的 return value 决定."

时间复杂度 O(n)，相对于每个 node 来讲，只会被函数调用和计算一次。

另一种时间复杂度的分析方式是，这题的递归结构不过是个 post-order traversal，遍历的复杂度当然是 O(n).

想到这，迭代的写法也比较明显了，写个 post-order traversal 就行。

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

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if(left != null && right != null) return root;
        else return (left == null) ? right : left;
    }
}

一种可能的迭代的写法是借鉴了我们教授 Martin Farach-Colton 的那篇 The LCA Problem Revisited 的 idea，就是先对 Tree 做 pre-processing 然后用 array 保存过渡结果方便快速 query.

其实就是 inorder pre-process 了一遍之后，把 binary tree 当 BST 用。因为 in-order 的 index 就像 BST 里的大小一样，可以直接确定几个节点在树中的相对位置。同时因为我们都是从 root 开始一层一层往下搜索的，也能保证每次循环的 root 都一定 valid.

这个代码的优点是如果做多次 query 的话有一个 pre-processing 的缓存可以很快返回结果；缺点就是多了个 pre-processing 的过程，query 次数少的时候不占便宜。

这个代码可以 AC，基本思路就是先跑一遍 inorder traversal 记录下每个 node 在整个树里面对应的位置；利用 hashmap 对每个 node 实现均摊复杂度 O(1) 的查找，然后根据对应的节点 index 判断 p，q 相对于 root 在 tree 里的位置关系。

中间跑了一次迭代版的 binary tree inorder traversal.

这两个代码都是一次写完直接 AC 的。。。Tree的问题只要思路不搞错可真容易过啊。。。

这个写法只能算是个有意思的迭代思路，空间时间耗费都挺大的，代码量也长，如果追求速度与效率的话，就不要用这个写法骗自己。。

不过如果在同一个 Tree 上要跑好多次 LCA，这个做法还是比较可取的~

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

        HashMap<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();

        TreeNode cur = root;
        int index = 0;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            map.put(node, index++);
            cur = node.right;
        }

        return getLCA(root, p, q, map);
    }

    private TreeNode getLCA(TreeNode root, TreeNode p, TreeNode q, HashMap<TreeNode, Integer> map){
        if(root == null) return root;
        if(root.val == p.val) return p;
        if(root.val == q.val) return q;

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

        return root;
    }

给一个 二叉树 ， 求最深节点的最小公共父节点。

http://www.1point3acres.com/bbs/thread-199739-1-1.html

       1
      / \
     2   3
        / \
       4   5

    return 3

       1
      / \
     2   3
    /   / \
   6   4   5

   return 1

先用 recursive ， 很快写出来了， 要求用 iterative.

这题的关键点只有一个：意识到只需要求最底层 level 最左面和最右面节点的 LCA 就可以了。

因此这个问题的递归与迭代就变成了两个子问题：

  • 如何递归求 level order 和 LCA

  • 如何迭代求 level order 和 LCA

白板上写了一遍，都不难，和这章前面以及 level order 的内容完全一样，就不进一步贴代码了。

Previous各种 Binary Tree 定义Next三序遍历，vertical order

Last updated