if (temp.Right == null || temp.Right == lastvisit) {
Console.WriteLine(temp.Element); }
else if (temp.Left == lastvisit) {
stack.Push(temp); temp = temp.Right; stack.Push(temp); while (temp != null) {
if (temp.Left != null)
stack.Push(temp.Left); temp = temp.Left; } } } }
//中序遍历，类似于前序遍历 static void InOrder(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) {
temp = (BinNode)stack.Pop(); Console.WriteLine(temp.Element); if (temp.Right != null) {
temp = temp.Right; stack.Push(temp); while (temp != null) {
if (temp.Left != null)
stack.Push(temp.Left); temp = temp.Left;
} } } }
6.在二叉树中找出和为某一值的所有路径
算法思想：这道题目的苦恼在于，如果用递归，只能打出一条路径来，其它符合条件的路径打不出来。
为此，我们需要一个Stack，来保存访问过的节点，即在对该节点的递归前让其进栈，对该节点的递归结束后，再让其出栈——深度优先原则（DFS）。
此外，在递归中，如果发现某节点（及其路径）符合条件，如何从头到尾打印是比较头疼的，因为DFS使用的是stack而不是queue，为此我们需要一个临时栈，来辅助打印。
static void FindBinNode(BinNode root, int sum, Stack stack) {
if (root == null) return;
stack.Push(root.Element); //Leaf
if (root.IsLeaf()) {
if (root.Element == sum) {
Stack tempStack = new Stack(); while (stack.Count > 0) {
tempStack.Push(stack.Pop()); }
while (tempStack.Count > 0) {
Console.WriteLine(tempStack.Peek()); stack.Push(tempStack.Pop()); }
Console.WriteLine(); } }
if (root.Left != null)
FindBinNode(root.Left, sum - root.Element, stack); if (root.Right != null)
FindBinNode(root.Right, sum - root.Element, stack); stack.Pop();
}
7.怎样编写一个程序，把一个有序整数数组放到二叉树中？
算法思想：我们该如何构造这棵二叉树呢？当然是越平衡越好，如下所示： //// arr[0]
//// arr[1] arr[2] //// arr[3] arr[4] arr[5] 相应编码如下：
public static void InsertArrayIntoTree(int[] arr, int pos, ref BinNode root) {
root = new BinNode(arr[pos], null, null); root.Element = arr[pos];
//if Left value less than arr length if (pos * 2 + 1 > arr.Length - 1) {
return; } else {
InsertArrayIntoTree(arr, pos * 2 + 1, ref root.Left); }
//if Right value less than arr length if (pos * 2 + 2 > arr.Length - 1) {
return; } else {
root.Right = new BinNode(arr[pos * 2 + 2], null, null); InsertArrayIntoTree(arr, pos * 2 + 2, ref root.Right); } }
8.判断整数序列是不是二叉搜索树的后序遍历结果
比如，给你一个数组： int a[] = [1, 6, 4, 3, 5] ，则F(a) => false
算法思想：在后续遍历得到的序列中，最后一个元素为树的根结点。从头开始扫描这个序列，比根结点小的元素都应该位于序列的左半部分；从第一个大于跟结点开始到跟结点前面的一个元素为止，所有元素都应该大于跟结点，因为这部分元素对应的是树的右子树。根据这样的划分，把序列划分为左右两部分，我们递归地确认序列的左、右两部分是不是都是二元查找树。
由于不能使用动态数组，所以我们每次递归都使用同一个数组arr，通过start和length来模拟“部分”数组。
public static bool VerifyArrayOfBST(int[] arr, int start, int length) {
if (arr == null || arr.Length == 0 || arr.Length == 1) {
return false; }
int root = arr[length + start - 1]; int i = start;
for (; i < length - 1; i++) {
if (arr[i] >= root) break; }
int j = i;
for (; j < length - 1; j++) {
if (arr[j] < root) return false; }
bool left = true; if (i > start) {
left = VerifyArrayOfBST(arr, start, i - start); }
bool right = true; if (j > i) {
right = VerifyArrayOfBST(arr, i, j - i + 1); }
return left && right; }
9.求二叉树的镜像
算法1：利用上述遍历二叉树的方法（比如说前序遍历），把访问操作修改为交
换左右节点的逻辑：
static void PreOrder(ref BinNode root) {
if (root == null) return;
//visit current node
BinNode temp = root.Left; root.Left = root.Right; root.Right = temp;
PreOrder(ref root.Left); PreOrder(ref root.Right); }
算法2：使用循环也可以完成相同的功能。 static void PreOrder2(ref BinNode root) {
if (root == null) return;
Stack stack = new Stack(); stack.Push(root);
while (stack.Count > 0) {
//visit current node
BinNode temp = root.Left; root.Left = root.Right; root.Right = temp; if (root.Left != null)
stack.Push(root.Left); if (root.Right != null)
stack.Push(root.Right); } }
10.一棵排序二叉树（即二叉搜索树BST），令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。
算法思想：最小最大节点分别在最左下与最右下节点，O(N) static BinNode Find(BinNode root)
算法大全-面试题-数据结构
