}
上述程序的逻辑是，只要当前节点root的Left和Right深度差不超过1，就递归判断Left和Right是否也符合条件，直到为Left或Right为null，这意味着它们的深度为0，能走到这一步，前面必然都符合条件，所以整个二叉树都符合条件。
4.设计一个算法，找出二叉树上任意两个节点的最近共同父结点，复杂度如果是O(n2)则不得分。
本题网上有很多算法，都不怎么样。这里提出包氏的两个算法：
算法1：做一个容器，我们在遍历二叉树寻找节点的同时，把从根到节点的路径扔进去（两个节点就是两个容器）。由于根节点最后一个被扔进去，但我们接下来又需要第一个就能访问到它——后进先出，所以这个容器是一个栈。时间复杂度O(N)，空间复杂度O(N)。
static bool GetPositionByNode(BinNode root, BinNode node, ref Stack stack) {
if (root == null) return false; if (root == node) {
stack.Push(root); return true; } if (GetPositionByNode(root.Left, node, ref stack) || GetPositionByNode(root.Right, node, ref stack)) {
stack.Push(root); return true; }
return false; }
然后我们要同时弹出这两个容器的元素，直到它们不相等，那么之前那个相等的元素就是我们要求的父亲节点。
static BinNode FindParentNode(BinNode root, BinNode node1, BinNode node2) {
Stack stack1 = new Stack();
GetPositionByNode(root, node1, ref stack1); Stack stack2 = new Stack();
GetPositionByNode(root, node2, ref stack2); BinNode tempNode = null;
while (stack1.Peek() == stack2.Peek()) {
tempNode = (BinNode)stack1.Pop(); stack2.Pop(); }
return tempNode; }
算法2：如果要求o(1)的空间复杂度，就是说，只能用一个变量来辅助我们。 我们选择一个64位的整数，然后从1开始，从左到右逐层为二叉树的每个元素赋值，root对应1，root.Left对应2，root.Right对应3，依次类推，而不管实际这个位置上是否有节点，我们发现两个规律： //// 1 //// 2 3 //// 4 5 6 7 //// 8 9 10
如果要找的是5和9位置上的节点。
我们发现，它们的二进制分别是101和1001，右移1001使之与101位数相同，于是1001变成了100（也就是9的父亲4）。 这时101和100（也就是4和5位于同样的深度），我们从左往右找，101和100具有2位相同，即10，这就是我们要找的4和5的父亲，也就是9和5的最近父亲。
由上面观察，得到算法：
1)将找到的两个节点对应的数字
static bool GetPositionByNode(BinNode root, BinNode node, ref int pos) {
if (root == null) return false; if (root == node) return true; int temp = pos;
//这么写很别扭，但是能保证只要找到就不再进行下去 pos = temp * 2;
if (GetPositionByNode(root.Left, node, ref pos)) {
return true; } else {
//找不到左边找右边 pos = temp * 2 + 1;
return GetPositionByNode(root.Right, node, ref pos); } }
2)它们的二进制表示，从左向右逐一比较，直到一个结束或不再相同，则最大的相同子串，就是我们需要得到的最近父亲所对应的位置K。 static int FindParentPosition(int larger, int smaller) {
if (larger == smaller) return larger;
int left = GetLen(larger) - GetLen(smaller); while (left > 0) {
larger = larger >> 1; left--; }
while (larger != smaller) {
larger = larger >> 1; smaller = smaller >> 1; }
return smaller; }
static int GetLen(int num) {
int length = 0; while (num != 0) {
num = num >> 1; length++; }
return length; }
3)第3次递归遍历，寻找K所对应的节点。
函数GetNodeByPosition的思想是，先算出k在第几层power，观察k的二进制表示，比如说12，即1100，从左向右数第一个位1不算，还剩下100，1表示向右走，0表示向左走，于是从root出发，1->3->6->12。 static BinNode GetNodeByPosition(BinNode root, int num) {
if (num == 1) return root;
int pow = (int)Math.Floor(Math.Log(num, 2)); //1 return 0, 2-3 return 1, 4-7 return 2
//第一个位不算 num -= 1 << pow; while (pow > 0) {
if ((num & 1 << (pow - 1)) == 0) root = root.Left; else
root = root.Right; pow--; }
return root; }
总结上面的3个步骤：
static BinNode FindParentNode(BinNode root, BinNode node1, BinNode node2) {
int pos1 = 1;
GetPositionByNode(root, node1, ref pos1); int pos2 = 1;
GetPositionByNode(root, node2, ref pos2); int parentposition = 0; if (pos1 >= pos2) {
parentposition = FindParentPosition(pos1, pos2); }
else //pos1 parentposition = FindParentPosition(pos2, pos1); } return GetNodeByPosition(root, parentposition); } 5.如何不用递归实现二叉树的前序/后序/中序遍历？ 算法思想：三种算法的思想都是让root的Left的Left的Left全都入栈。所以第一个while循环的逻辑，都是相同的。 下面详细分析第2个while循环，这是一个出栈动作，只要栈不为空，就始终要弹出栈顶元素，由于我们之前入栈的都是Left节点，所以每次在出栈的时候，我们都要考虑Right节点是否存在。因为前序/后序/中序遍历顺序的不同，所以在具体的实现上有略为区别。 1)前序遍历 这个是最简单的。 前序遍历是root->root.Left->root.Right的顺序。 因为在第一个while循环中，每次进栈的都可以认为是一个root，所以我们直接打印，然后root.Right和root.Left先后进栈，那么出栈的时候，就能确保先左后 右的顺序。 static void PreOrder(BinNode root) { Stack stack = new Stack(); BinNode temp = root; //入栈 while (temp != null) { Console.WriteLine(temp.Element); if (temp.Right != null) stack.Push(temp.Right); temp = temp.Left; } //出栈，当然也有入栈 while (stack.Count > 0) { temp = (BinNode)stack.Pop(); Console.WriteLine(temp.Element); while (temp != null) { if (temp.Right != null) stack.Push(temp.Right); temp = temp.Left; } } } //后序遍历比较麻烦，需要记录上一个访问的节点，然后在本次循环中判断当前节点的Right或Left是否为上个节点，当前节点的Right为null表示没有右节点。 static void PostOrder(BinNode root) { Stack stack = new Stack(); BinNode temp = root; //入栈 while (temp != null) { if (temp != null) stack.Push(temp); temp = temp.Left; } //出栈，当然也有入栈 while (stack.Count > 0) { BinNode lastvisit = temp; temp = (BinNode)stack.Pop();
算法大全-面试题-数据结构
