目录：
1.二叉树三种周游（traversal）方式：
2.怎样从顶部开始逐层打印二叉树结点数据
3.如何判断一棵二叉树是否是平衡二叉树
4.设计一个算法，找出二叉树上任意两个节点的最近共同父结点，复杂度如果是O(n2)则不得分。
5.如何不用递归实现二叉树的前序/后序/中序遍历？
6.在二叉树中找出和为某一值的所有路径
7.怎样编写一个程序，把一个有序整数数组放到二叉树中？
8.判断整数序列是不是二叉搜索树的后序遍历结果
9.求二叉树的镜像
10.一棵排序二叉树（即二叉搜索树BST），令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。
11.把二叉搜索树转变成排序的双向链表

首先写一个二叉树的C#实现，这是我们的基石：
public class BinNode
{
public int Element;
public BinNode Left;
public BinNode Right;
public BinNode(int element, BinNode left, BinNode right)
{
this.Element = element;
this.Left = left;
this.Right = right;
}

public bool IsLeaf()
{
return this.Left == null && this.Right == null;
}
}

1.二叉树三种周游（traversal）方式：
1）前序周游（preorder）：节点 –> 子节点Left（包括其子树） –> 子节点Right（包括其子树）
static void PreOrder(BinNode root)
{
if (root == null)
return;
//visit current node
Console.WriteLine(root.Element);
PreOrder(root.Left);
PreOrder(root.Right);
}

2）后序周游（postorder）：子节点Left（包括其子树） –> 子节点Right（包括其子树） –> 节点
static void PostOrder(BinNode root)
{
if (root == null)
return;
PostOrder(root.Left);
PostOrder(root.Right);
//visit current node
Console.WriteLine(root.Element);
}

3）中序周游（inorder）：子节点Left（包括其子树） –> 节点 –> 子节点Right（包括其子树）
static void InOrder(BinNode root)
{
if (root == null)
return;
InOrder(root.Left);
//visit current node
Console.WriteLine(root.Element);
InOrder(root.Right);
}

我们发现，三种周游的code实现，仅仅是访问当前节点的这条语句所在位置不同而已。

2.怎样从顶部开始逐层打印二叉树结点数据
有2种算法：
算法1：基于Queue来实现，也就是广度优先搜索（BFS）的思想
static void PrintTree1(BinNode root)
{
if (root == null) return;
BinNode tmp = null;
Queue queue = new Queue();
queue.Enqueue(root);
while (queue.Count > 0)
{
tmp = (BinNode)queue.Dequeue();
Console.WriteLine(tmp.Element);
if (tmp.Left != null)
queue.Enqueue(tmp.Left);
if (tmp.Right != null)
queue.Enqueue(tmp.Right);
}
}

话说，BFS和DFS思想本来是用于图的，但我们不能被传统的思维方式所束缚。

算法2：基于单链表实现
如果没有Queue给我们用，我们只好使用单链表，把每个节点存在单链表的Data中，实现如下：
public class Link
{
public Link Next;
public BinNode Data;
public Link(Link next, BinNode data)
{
this.Next = next;
this.Data = data;
}
}
看过了Queue的实现，我们发现永远是先出队1个（队头），然后入队2个（把出队的Left和Right放到队尾）。
对于单链表而言，我们可以先模拟入队——把first的Data所对应的Left和Right，先后插到second的后面，即second.Next和second.Next.Next位置，同时second向前走0、1或2次，再次到达链表末尾，这取决于Left和Right是否为空；然后我们模拟出队——first前进1步。
当first指针走不下去了，那么任务也就结束了。
static void PrintTree2(BinNode root)
{
if (root == null) return;
Link head = new Link(null, root);
Link first = head;
Link second = head;
while (first != null)
{
if (first.Data.Left != null)
{
second.Next = new Link(null, first.Data.Left);
second = second.Next;
}
if (first.Data.Right != null)
{
second.Next = new Link(null, first.Data.Right);
second = second.Next;
}
Console.WriteLine(first.Data.Element);
first = first.Next;
}
}

3.如何判断一棵二叉树是否是平衡二叉树
平衡二叉树的定义，如果任意节点的左右子树的深度相差不超过1，那这棵树就是平衡二叉树。
算法思路：先编写一个计算二叉树深度的函数GetDepth，利用递归实现；然后再递归判断每个节点的左右子树的深度是否相差1
static int GetDepth(BinNode root)
{
if (root == null)
return 0;
int leftLength = GetDepth(root.Left);
int rightLength = GetDepth(root.Right);
return (leftLength > rightLength
leftLength : rightLength) + 1;
}

注意这里的+1，对应于root不为空（算作当前1个深度）
static bool IsBalanceTree(BinNode root)
{
if (root == null)
return true;
int leftLength = GetDepth(root.Left);
int rightLength = GetDepth(root.Right);
int distance = leftLength > rightLength
leftLength – rightLength : rightLength – leftLength;