leetcode: Lowest Common Ancestor of a Binary Tree

问题描述

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

原问题链接：https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

 

问题分析

    这个问题和前面类似的求二叉搜索树不一样，它相对要难一些。因为在前面基于二叉搜索树查找最低父节点的时候可以根据当前节点的值和两个目标节点做比较，然后根据它们值的大小作下一步的选择。而这里的数据结构不在是二叉搜索树，没法根据每个节点的值来作为判断的依据了。那么该怎么来处理这个问题呢？

 

方法一：

    这种办法是基于这么一个设想。对于一棵二叉树来说，如果需要找两个节点的最低公共父节点，假设它们有指向父节点的引用，那么可以先从一个节点开始，不断向上遍历一直到根节点，并将这些遍历过的节点通过某个数据结构保存起来。然后从另外一个节点也这样开始向上遍历，每次遍历的节点和前面那个节点遍历的所有节点比较，如果有碰到第一个相同的则表示这个节点就是我们要找到目标节点。比如说我们有如下的树：

 

     如果按照上述的思路，我们的节点8往上到根节点遍历的节点是{8, 4, 2, 1}，而节点6往上遍历到根节点的所有节点是{6, 3, 1}。所以它们的最低公共父节点是1，也就是根节点。

    现在，假设我们已经有了一个节点到根节点的遍历路径，我们可以用一个集合(Set)来保存它们，对于另外一个节点，只要它往上遍历的时候碰到的第一个在前面集合中存在的元素，则找到了目标节点。

    上面这部分能够得以进行是基于一个假设的前提，就是可以通过某种途径来得到每个节点的父节点信息。在现在的二叉树结构里并没有直接提供这个引用。那么该怎么获得这个信息呢？另外，获得了这个信息之后，又该怎么来保存它和它的父节点信息以方便从该节点往上遍历呢？这个时候就需要借用一下一些二叉树遍历的方法了。 

    在所有二叉树遍历的算法过程中，如果用非递归的方式来遍历的话，最简单的大概就算是层次化的遍历树了。关于二叉树的层次化遍历在我之前的文章中也有讨论过。为什么要选择这种层次化遍历的方式呢？因为一个就是如果递归的去遍历一些树结构在树的层次比较深的时候容易导致递归的堆栈溢出，而采用层次化遍历不会有这个问题。另外一个，我们在遍历每个节点的时候需要将该节点和它的子节点关系建立起来并保存到一个结构中，采用这种方式比较直观。每次遍历一层的时候就将该层的节点和它们字节点映射起来。

    在怎么去遍历树的的方式定下来之后，现在需要定下来的就是怎么保存每个节点和它们父节点的关系了。一种比较有效的保存办法就是利用一个map，里面的key和value都是TreeNode。为什么选择用map呢？因为对于树里面的每个节点，它都是唯一的，如果以它们作为key是不会存在有冲突的。另外，它们每个节点都有父节点，对于根节点这个特殊情况，我们可以定义它的父节点为null。如果我们要从某个往上遍历的时候只需要node = map.get(node)就可以得到了。通过这样的不断循环来向上走。

     通过这一通讨论，我们有了一个基本的思路。概括起来如下，首先通过层次遍历将每个节点和它的子节点之间的关系映射到一个map里。然后通过一个节点利用map的映射关系向上遍历一直到根节点。将它遍历过的所有节点保存在一个set里。然后另外一个也利用map的映射关系向上遍历，但是遍历的时候判断自己遍历的元素是否在前面的set中，如果找到了，则该节点就是最低公共父节点。按照这个思路实现的代码如下：

 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || p == null || q == null) return null;
        Map<TreeNode, TreeNode> map = buildPath(root);
        Set<TreeNode> set = new HashSet<>();
        TreeNode node = p;
        while(node != null) {
            set.add(node);
            node = map.get(node);
        }
        node = q;
        while(node != null) {
            if(set.contains(node)) return node;
            node = map.get(node);
        }
        return null;
    }
    
    Map<TreeNode, TreeNode> buildPath(TreeNode node) {
        Map<TreeNode, TreeNode> map = new HashMap<>();
        map.put(node, null);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        while(!queue.isEmpty()) {
            TreeNode tNode = queue.remove();
            if(tNode.left != null) {
                map.put(tNode.left, tNode);
                queue.add(tNode.left);
            }
            if(tNode.right != null) {
                map.put(tNode.right, tNode);
                queue.add(tNode.right);
            }
        }
        return map;
    }
}

    上述代码的时间复杂度也比较好推导，首先一个层次遍历，它的时间复杂度为O(N)，然后一个节点向上遍历，时间复杂度也为O(N)，另外一个节点的过程也类似。所以总体时间复杂度为O(N)。而空间复杂度主要是包含几个部分，首先是层次化遍历的时候要用到一个queue，空间为O(N)，保存映射关系的时候用到一个map，空间为O(N)，保存遍历路径节点的set，空间为O(N)，总体也是在O(N)的范围。所以总体来说这种方法的时间和空间复杂度还是在一个比较合理的范围。

 

方法二：

    上述的第一种方法总的来说还是步骤有点复杂，因为需要去遍历树来建立映射关系再获取从子节点到父节点的路径。有些地方如果没有想到的话还是比较难解决的。那么还有没有其他的思路呢？实际上还有一种比较简单直观的思路。就是递归的方式。我们可以这样来看，对于任意的一个节点来说，如果以它为根节点去找两个节点的最低公共父节点，首先需要的是找到它的左右子树中是否存在有要查找的两个节点中的一个。如果找到任意一个则返回，否则返回null。而在回溯的时候，对于这个最低公共子节点有一个特性，它必然左右子节点返回的值都不为空的，而其他节点则总会有一个为空。所以在回溯的时候，如果它们中间有一个非空则返回不空的那个，如果左右子树的节点都不空则返回当前节点。这样可以得到如下的代码：

 

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) { return root; }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left!=null && right!=null) { return root; }
        return left!=null ? left : right;
    }
}

    这种方式实现的效率相对来说更高。因为它总的来说只需要遍历树一遍，然后在回溯的时候将结果过滤出来。它的时间复杂度也是O(N)。从使用的空间来说，因为要用到堆栈来递归的调用，在树的层次比较深的时候容易造成栈溢出。当然，这种实现的方式是最简洁的。

 

总结

     求二叉树的最低公共父节点算是一个讨论过很多的问题了。对于它的解法有很多。对于第一种遍历树记录节点父子关系，然后再通过节点遍历来查找的方式比较容易想到一点。只是用到各种数据结构会比较繁琐。而第二种通过递归回溯求解的时候需要定义清楚它们的递归关系并且回溯的时候对结果进行过滤。这种方式比较巧妙，值得反复推敲。

 

参考材料

http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/

http://articles.leetcode.com/lowest-common-ancestor-of-a-binary-tree-part-i

http://articles.leetcode.com/lowest-common-ancestor-of-a-binary-tree-part-ii