LCA问题

LCA是tree 类型的问题中的高频题：

• 有父节点
• 没有父节点的
• 是bst的
• 普通二叉树的

LCA解决问题的核心是找到一个节点，其中a，b节点分别在该节点的左右子树中。

用post-order traverse 可以达到O(n)的复杂度。

还有一个思路，就是先用in-order 的顺序preprocessing 整个树，用hashmap记录下来每个node的相对顺序。然后整个数就可以类比一个BST来做。

LCA of Binary Tree with Parent pointer

public TreeNode LCA（TreeNode p, TreeNode q) {
    if(p == null || q == null) {
        return p == null ? q : p;
    }

    while(p.parent != q.parent) {
        p = p.parent;
        q = q.parent;
    }

    return p.parent;
}

Lowest Common Ancestor of a Binary Search Tree

有两种情况：

• 一个节点是另外一个节点的父节点，那么LCA就是depth高的那个节点
• 两个节点分别在node A的左右子树里面，那么LCA就是就是node A.

public TreeNode findBSTLCANode(TreeNoe root, TreeNode p, TreeNode q) {
    if(root == null) {
        return root;
    }

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

    return root;
}

迭代写法：

利用尾递归(tail recursion)的性质：尾调用的重要性在于它可以不在调用栈上面添加一个新的堆栈帧——而是更新它，如同迭代一般。

public TreeNode findBSTLCANode(TreeNoe root, TreeNode p, TreeNode q) {
    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

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

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

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

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

public TreeNode LCA(TreeNoe root, TreeNode p, TreeNode q) {
    // base case
    if(root == null || root == p || root == q) {
        return root;
    }

    // post-order 
    TreeNode left = LCA(root.left, p, q);
    TreeNode right = LCA(root.right, p, q);

    // find LCA
    if(left != null && right != null) {
        return root;
    } else if(left != null || right != null) {
        return left != null ? left : right;
    }
}

求最深节点的LCA

FB的面经题

       1
      / \
     2   3
        / \
       4   5

    return 3

       1
      / \
     2   3
    /   / \
   6   4   5

   return 1

level order 找到最深层的head node和tail node, 再去求其LCA

找出最深层的head和tail节点，用一个map来track 节点到父节点的映射。 如果head 和tail相等，说明最深层就一个节点，如果不等，分别从map里向parent节点搜索，知道发现一个公共的节点即为LCA。

public TreeNode deepLevelLCA(TreeNode root) {
    if(root == null) {
        return null;
    }

    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    // node -> parent
    HashMap<TreeNode, TreeNode> map = new HashMap<>();
    map.put(root, null);

    TreeNode head = null, tail = null;
    while(!q.isEmpty()) {
        int size = q.size();
        head = null; 
        tail = null;
        for(int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            if(head == null) {
                head == node;
            }
            if(size == 0) {
                tail = node;
            }

            if (node.left != null) {
                q.offer(node.left);
                map.put(node.left, node);
            }
            if (node.right != null) {
                q.offer(node.right);
                map.put(node.right, node);
            }
        }
    }
    // from the bottom up search
    while(head != tail) {
        head = map.get(head);
        tail = map.get(tail);
    }
    return head;

}

DFS解法：

post-order + return Result class

class Result {
    int depth;
    TreeNode lca;

    public Result(int depth, TreeNode node) {
        this.depth = depth;
        this.lca = node;
    }
}

public TreeNode LCAofDeepestLevel(TreeNode root) {
    Result result = find(root, 0);
    return result.lca;
}

public Result find(TreeNode root, int depth) {
    // the depth of the highest level is 0
    if(root == null) {
        return new Result(root, -1);
    }

    Result left = find(root.left, depth + 1);
    Result right = find(root.right, depth + 1);

    // LCA在不在当前节点
    if(left.depth == right.depth) {
        return new Result(left.depth == -1 ? depth : left.depth, root);
    } else {
        return new Result(Math.max(left.depth, right.depth), left.depth > right.depth ? left.lca : right.lca);
    }
}