微软亚洲工程院面试题：寻找两个二叉树节点的最近祖先

给定一颗二叉树，并指定二叉树中任意两个节点，要求找出这两个节点在二叉树中的最近祖先，假定二叉树每个节点都有一个指向其父节点的指针，图中没有画出来，要求算法的空间复杂度必须是O(1), 时间复杂度为O(h)。例如给定下面二叉树：

如果指定的两个节点是401和257，那么他们的最近祖先就是节点1，如果指定节点是401， 29， 那么他们的最近祖先就是节点7.

这道算法题是早年我面试微软亚洲工程院时，大boss给我出的最后一道算法题，那天面试时长至少六小时，大概有六轮，搞定这道Boss给我出的这道算法题后，当天晚上微软的offer就发到了我邮箱里，回想起来，当时那种成就感和喜悦之情，至今还能体察得到。

这道题要想在四十分钟，并且伴有心理压力的情况之下找到合适的算法，其实是不容易的。算法步骤是这样的：

1， 从给定的节点出发，根据其父节点往上走，一直走到根节点为止，先确定两个节点在二叉树中的高度。例如节点401经过第一步后得到的高度是4，节点29高度是3.

2， 从高度大的节点出发，通过父指针往上走，一直走到高度与另个一高度较小的节点高度一样为止。例如从节点401开始，先回到父节点1，因为此时节点1的高度与节点29的高度一样，都是3.

3，两个节点分别往上走一步，然后判断是否重合，如果重合，那么当前节点就是两节点的最近祖先，若不然则继续重复步骤3，例如从节点1，和节点29开始，每往上走一步就判断是否重合，那么他们分别往上走两步后，将会在节点7相遇，因此，节点7将是节点401和节点29的最近共同祖先。

该算法不需要分配内存，所以空间复杂度为O(1), 算法第一步需要从节点逆回到根节点以便获得节点的高度，所需时间为二叉树的高，也就是O(h).第三步是一步一步的回溯，最差情况下，是回溯到根节点就可以停止，所以所需时间也是二叉树的高，也就是O(h), 综合起来，我们的算法符合题目要求。接着我们给出算法的具体实现如下：

public class LowestCommonAscestor {
    private TreeNode node1 = null;
    private TreeNode node2 = null;

    public LowestCommonAscestor(TreeNode n1, TreeNode n2) {
        this.node1 = n1;
        this.node2 = n2;
    }

    private int findNodeHeight(TreeNode n) {
        int h = 0;
        while (n.parent != null) {
            h++;
            n = n.parent;
        }

        return h;
    }

    private TreeNode retrackByHeight(TreeNode n,int h) {
        while (n.parent != null && h > 0) {
            h--;
            n = n.parent;
        }

        return n;
    }

    private TreeNode traceBack(TreeNode n1, TreeNode n2) {
        while (n1 != n2) {
            if (n1 != null) {
                n1 = n1.parent;
            }

            if (n2 != null) {
                n2 = n2.parent; 
            }
        }

        return n1;
    }

    public TreeNode getLCA() {
        int h1 = findNodeHeight(node1);
        int h2 = findNodeHeight(node2);

        if (h1 > h2) {
            node1 = retrackByHeight(node1, h1 - h2);
        } else if (h1 < h2){
            node2 = retrackByHeight(node2, h2 - h1);
        }

        return traceBack(node1, node2);
    }
}

LowestCommonAscestor用于实现上面所说的算法，它的构造函数要求输入量节点，也就是要查找最近共同祖先的两个节点。findNodeHeight的目的是依据给定节点查找该节点的高，其对应与算法第一步，retrackByHeight作用是根据给定节点和高度，利用parent指针逐级回溯，也就是对应算法步骤2，traceBack的目的是根据两个给定节点，一级一级的往上走，直到两点重合位置，其对应的是给定算法步骤3.

我们再看看二叉树构造的代码（BTreeBuilder.java)：

import java.util.HashMap;


public class BTreeBuilder {
    private HashMap<Integer, Integer> nodeMap = new HashMap<Integer, Integer>();
    private TreeNode root = null;
    private TreeNode node1 = null;
    private TreeNode node2 = null;

    public BTreeBuilder(int[] inorder, int[] preorder) {
        for (int i = 0; i < inorder.length; i++) {
            nodeMap.put(inorder[i], i);
        }

        buildTree(preorder);
    }

    private void buildTree(int[] preorder) {
        if (root == null) {
            root = new TreeNode(preorder[0]);
        }

        for (int i = 1; i < preorder.length; i++) {
            int val = preorder[i];
            TreeNode current = root;
            while (true) {
                TreeNode node = null;

                if (nodeMap.get(val) < nodeMap.get(current.val)) {
                    if (current.left != null) {
                        current = current.left;
                    } else {
                        node = new TreeNode(val);
                        current.left = node;
                        setNode(node);
                        node.parent = current;
                        break;
                    }
                } else {
                    if (current.right != null) {
                        current = current.right;
                    } else {
                        node = new TreeNode(val);
                        current.right = node;
                        node.parent = current;
                        setNode(node);
                        break;
                    }
                }

            }
        }
    }

    private void setNode(TreeNode node) {
        if (node != null && node.val == 401) {
            node1 = node;
        }

        if (node != null && node.val == 29) {
            node2 = node;
        }
    }

    public TreeNode getNode1() {
        return node1;
    }

    public TreeNode getNode2() {
        return node2;
    }

    public TreeNode getTreeRoot() {
        return root;
    }
}

它的实现逻辑变化不大，只是加了一些代码用于获取指定节点401和29.最后我们再看看主入口处的代码：

import java.util.ArrayList;


public class BinaryTree {
   public static void main(String[] s) {

       int[] inorder = new int[]{28, 271, 0, 6, 561, 17, 3, 314, 2, 401, 641, 1, 257, 7, 278, 29};
       int[] preorder= new int[] {314, 6, 271, 28, 0, 561, 3, 17, 7, 2, 1, 401, 641, 257, 278, 29};
       BTreeBuilder treeBuilder = new BTreeBuilder(inorder, preorder);
       TreeNode n1 = treeBuilder.getNode1();
       TreeNode n2 = treeBuilder.getNode2();

       LowestCommonAscestor lca = new LowestCommonAscestor(treeBuilder.getNode1(), treeBuilder.getNode2());
       TreeNode ascester = lca.getLCA();

       System.out.println("The lowest common anscestor of node " + n1.val + "," + n2.val + " is " + ascester.val);
   }
}

代码首先构造了给定二叉树，然后构造一个LowestCommonAscestor对象，并把要查找共同祖先的两个节点提交给它的构造函数，接着调用该类的getLCA接口获得两节点的最近共同祖先。上面代码执行后，打印出的结果如下:
The lowest common anscestor of node 401,29 is 7

由此可见，我们代码对算法的实现应该是正确的。更详细的算法讲解和代码调试请参看视频。

更多技术信息，包括操作系统，编译器，面试算法，机器学习，人工智能，请关照我的公众号：