更详细的讲解和代码调试演示过程，请参看视频
用java开发C语言编译器
更详细的讲解和代码调试演示过程，请参看视频
如何进入google,算法面试技能全面提升指南
如果你对机器学习感兴趣，请参看一下链接：
机器学习：神经网络导论
更详细的讲解和代码调试演示过程，请参看视频
Linux kernel Hacker, 从零构建自己的内核
给定一颗二叉树，并指定二叉树中任意两个节点，要求找出这两个节点在二叉树中的最近祖先，假定二叉树每个节点都有一个指向其父节点的指针，图中没有画出来，要求算法的空间复杂度必须是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
由此可见，我们代码对算法的实现应该是正确的。更详细的算法讲解和代码调试请参看视频。
更多技术信息，包括操作系统，编译器，面试算法，机器学习，人工智能，请关照我的公众号： 