目錄： 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 nodeConsole.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 nodeConsole.WriteLine(root.Element);}3）中序周游（inorder）：子節點Left（包括其子樹） –> 節點 –> 子節點Right（包括其子樹）
static void InOrder(BinNode root){if (root == null)return;InOrder(root.Left);//visit current nodeConsole.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 > rightLengthleftLength : 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 > rightLengthleftLength – rightLength : rightLength – leftLength;if (distance > 1)return false;elsereturn IsBalanceTree(root.Left) && IsBalanceTree(root.Right);}上述程序的邏輯是，只要當前節點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 ////4567 ////8910 如果要找的是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;elseroot = 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<pos2{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();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);//Leafif (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 lengthif (pos * 2 + 1 > arr.Length – 1){return;}else{InsertArrayIntoTree(arr, pos * 2 + 1, ref root.Left);}//if Right value less than arr lengthif (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 nodeBinNode 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 nodeBinNode 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){BinNode min = FindMinNode(root);BinNode max = FindMaxNode(root);double find = (double)(min.Element + max.Element) / 2;return FindNode(root, find);}static BinNode FindMinNode(BinNode root){BinNode min = root;while (min.Left != null){min = min.Left;}return min;}static BinNode FindMaxNode(BinNode root){BinNode max = root;while (max.Right != null){max = max.Right;}return max;}遞歸尋找BST的節點，O(logN)。static BinNode FindNode(BinNode root, double mid){//如果小于相等，則從右邊找一個最小值if (root.Element <= mid){if (root.Right == null)return root;BinNode find = FindNode(root.Right, mid);//不一定找得到return find.Element < midroot : find;}//如果大于，則找到Leftelse //temp.Element > find{if (root.Left == null)return root;BinNode find = FindNode(root.Left, mid);//不一定找得到return find.Element < midroot : find;}}11.把二叉搜索樹轉變成排序的雙向鏈表，如 ////13 ////1015 //// 51117 ////1622 轉變為Link：5=10=11=13=15=16=17=22 算法思想：這個就是中序遍歷啦，因為BST的中序遍歷就是一個從小到大的訪問順序。局部修改中序遍歷算法，于是有如下代碼：
static void ConvertNodeToLink(BinNode root, ref DoubleLink link){if (root == null)return;BinNode temp = root;if (temp.Left != null)ConvertNodeToLink(temp.Left, ref link);//visit current nodelink.Next = new DoubleLink(link, null, root);link = link.Next;if (temp.Right != null)ConvertNodeToLink(temp.Right, ref link);}但是我們發現，這樣得到的Link是指向雙鏈表最后一個元素22，而我們想要得到的是表頭5，為此，我們不得不額外進行while循環，將指針向前移動到表頭：
static DoubleLink ReverseDoubleLink(BinNode root, ref DoubleLink link){ConvertNodeToLink(root, ref link);DoubleLink temp = link;while (temp.Prev != null){temp = temp.Prev;}return temp;}這么寫有點蠢，為什么不直接在遞歸中就把順序反轉呢?于是有算法2：
算法2：觀察算法1的遞歸方法，訪問順序是Left -> Root –> Right，所以我們要把訪問順序修改為Right -> Root –> Left。 此外，算法的節點訪問邏輯，是連接當前節點和新節點，同時指針link向前走，即5=10=11=13=15=16=17=22=link 代碼如下所示： link.Next = new DoubleLink(link, null, root); link = link.Next; 那么，即使我們顛倒了訪問順序，新的Link也只是變為：22=17=16=15=13=11=10=5=link。 為此，我們修改上面的節點訪問邏輯——將Next和Prev屬性交換： link.Prev = new DoubleLink(null, link, root); link = link.Prev; 這樣，新的Link就變成這樣的順序了：link=5=10=11=13=15=16=17=22 算法代碼如下所示：
static void ConvertNodeToLink2(BinNode root, ref DoubleLink link){if (root == null)return;BinNode temp = root;if (temp.Right != null)ConvertNodeToLink2(temp.Right, ref link);//visit current nodelink.Prev = new DoubleLink(null, link, root);link = link.Prev;if (temp.Left != null)ConvertNodeToLink2(temp.Left, ref link);}新聞熱點
疑難解答
