二叉樹的常見問題有如下幾個，如果解決好了，就跟鏈表一樣輕松：唯一不一樣的是，二叉樹是非線性結構。常見的問題如下 1.二叉樹三種周游（traversal）方式： 2.怎樣從頂部開始逐層打印二叉樹結點數據 3.如何判斷一棵二叉樹是否是平衡二叉樹 4.設計一個算法，找出二叉樹上任意兩個節點的最近共同父結點，復雜度如果是O(n2)則不得 分。 5.如何不用遞歸實現二叉樹的前序/後序/中序遍歷？ 6.在二叉樹中找出和為某一值的所有路徑 7.怎樣編寫一個程序，把一個有序整數數組放到二叉樹中？ 8.判斷整數序列是不是二叉搜索樹的後序遍歷結果 9.求二叉樹的鏡像 10.一棵排序二叉樹（即二叉搜索樹BST），令 f=(最大值+最小值)/2，設計一個算法，找出距 離f值最近、大於f值的結點。復雜度如果是O(n2)則不得分。 11.把二叉搜索樹轉變成排序的雙向鏈表 12.打印二叉樹中的所有路徑（與題目5很相似） 解決思路： 1.二叉樹三種周游（traversal）方式：任何一本數據結構的書都有描述，略過； 2.怎樣從頂部開始逐層打印二叉樹結點數據？ 設置一個隊列，然後只要隊列不為空，將對首元素的左右孩子加入隊列（如果左右孩子不為空），然後將隊列的首元素出對即可，如下圖所示： 二叉樹如下圖所示： 那麼，整個過程如下： 自然，就輸出了a,b,c,d,e,f 3.如何判斷一個二叉樹是否是平衡的？ 太簡單了，利用遞歸就可以了：判斷根節點的左右子樹深度之差是否小於等於1(這裡需要用到求深度的方法)，如果是，根節點就是平衡的；然後，在判斷根節點的左孩子和右孩子是否是平衡的。如此繼續下去，直到遇見葉子節點。一旦不是，立刻返回false; 計一個算法，找出二叉樹上任意兩個節點的最近共同父結點，復雜度如果是O(n2)則不得分 首先找到這兩個點key1和key2，並且記錄下找到這兩個點的路徑Path1和Path2。然後，找到第一個點k滿足，key1<k<key2就可以了。 如圖： 假設key1 = 5，key2 = 7，那麼顯然，Path1{8,6,5}, Path2{8,6,7}。滿足第一個key1<k<key2的k為6。故k = 6。 至於怎麼求出Path1和Path2，可以看問題12。 5.如何不用遞歸實現二叉樹的前序/後序/中序遍歷？（網易面試就問到了，悲劇了，當時一下子卡住了） 看看書，基本任何一本數據結構的書都有，主要利用棧。 6.在二叉樹中找出和為某一值的所有路徑？ 還是先解決12題目，訪問二叉樹到葉子節點的任意路徑。這個問題解決了，自然求和看是否滿足條件就可以了。 7.怎樣編寫一個程序，把一個有序整數數組放到二叉樹中？ 遞歸，還是利用遞歸： 設有int array[begin,end]，首先將array[(begin + end)/2]加入二叉樹，然後遞歸去做array[begin,(begin + end)/2 - 1]和array[(begin + end)/2 + 1, end]。注意寫好函數的形式就可以了。一切都很自然。 8.判斷整數序列是不是二叉搜索樹的後序遍歷結果？ 看看吧，後續遍歷是這樣做的：左右根，所以訪問的最有一個節點實際上就是整棵二叉樹的根節點root：然後，找到第一個大於該節點值的根節點b，b就是root右子樹最左邊的節點（大於根節點的最小節點）。那麼b前面的就是root的左子樹。既然是二叉搜索樹的遍歷結果，那麼在b和root之間的遍歷結果，都應該大於b。去拿這個作為判斷的條件。 9.求二叉樹的鏡像？ 還是利用遞歸：只要節點不為空，交換左右子樹的指針，然後在分別求左子樹的鏡像，再求右子樹的鏡像，直到節點為NULL。 10.一棵排序二叉樹（即二叉搜索樹BST），令 f=(最大值+最小值)/2，設計一個算法，找出距離f值最近、大於f值的結點。復雜度如果是O(n2)則不得分。 首先，在BST中，最小值就是最左邊的節點，最大值就是最右邊的節點。 在分別求出min和max後，求出f。然後利用查找，找出一個大於f的節點就可以了。 復雜度為logN。 11.把二叉搜索樹轉變成排序的雙向鏈表 12..打印二叉樹中的所有路徑 路徑的定義就是從根節點到葉子節點的點的集合。 還是利用遞歸：用一個list來保存經過的節點，如果已經是葉子節點了，那麼打印list的所有內容；如果不是，那麼將節點加入list，然後繼續遞歸調用該函數，只不過，入口的參數變成了該節點的左子樹和右子樹。 程序如下 解答1：自己看書了 解答2： //問題2：怎樣從頂部開始逐層打印二叉樹結點數據 void PrintAtLevel(BiTNode* root){ vector<BiTNode*> vector; vector.push_back(root); while(!vector.empty()){ BiTNode* tmp = vector.front(); if(tmp->lchild != NULL) vector.push_back(tmp->lchild); if (tmp->rchild != NULL) vector.push_back(tmp->rchild); cout << tmp->data << endl; vector.pop_back(); } } //問題3：如何判斷一棵二叉樹是否是平衡二叉樹 int isBalencedTree(treeNode* root){ if (root == NULL) return 0; int depth1 = getDepth(root->lchild); int depth2 = getDepth(root->rchild); if (depth1 == depth2 || depth1 == depth2 + 1 || depth1 == depth2 - 1) return 1; else return 0; int flag1 = isBalencedTree(root->lchild); int flag2 = isBalencedTree(root->rchild); if (flag1 && flag2) return 1; else return 0; } //問題4：設計一個算法，找出二叉樹上任意兩個節點的最近共同父結點，復雜度如果是O(n2) 則不得分。 int getPublicAncestors(treeNode* root,int key1,int key2){ treeNode* ptr = root; int path1[1000]; int pathLen1 = 0; while (ptr != NULL){ if (key1 == ptr->data){ path1[pathLen1] = ptr->data; pathLen1 ++; printArray(path1,pathLen1); break; } else if (ptr->data > key1){ path1[pathLen1] = ptr->data; pathLen1 ++; ptr = ptr->lchild; } else if (ptr->data < key1){ path1[pathLen1] = ptr->data; pathLen1 ++; ptr = ptr->rchild; } } ptr = root; int path2[1000]; int pathLen2 = 0; while (ptr != NULL){ if (key2 == ptr->data){ path2[pathLen2] = ptr->data; pathLen2 ++; printArray(path2,pathLen2); break; } else if (ptr->data > key2){ path2[pathLen2] = ptr->data; pathLen2 ++; ptr = ptr->lchild; } else if (ptr->data < key2){ path2[pathLen2] = ptr->data; pathLen2 ++; ptr = ptr->rchild; } } int i = pathLen1 - 1; //key1和key2有序， if (key2 < key1){ key2 = key2^key1; key1 = key2^key1; key2 = key2^key1; } for (; i > 0; i --){ if (key1 < path1[i] && path1[i]< key2){ int result = path1[i]; return result; } } } //問題6：在二叉樹中找出和為某一值的所有路徑 void FindPath(treeNode* root, int path[],int pathLen,int expectedSum, int currentSum){ if (root == NULL) return; currentSum += root->data; path[pathLen] = root->data; pathLen ++; if (currentSum == expectedSum && root->lchild == NULL && root->rchild == NULL){ printArray(path,pathLen); } if (root->lchild != NULL){ FindPath(root->lchild,path,pathLen,expectedSum,currentSum); } if (root->rchild != NULL){ FindPath(root- >rchild,path,pathLen,expectedSum,currentSum); } currentSum -= root->data; } //問題7：怎樣編寫一個程序，把一個有序整數數組放到二叉樹中？ void createTreeFromArray(int a[], int begin, int end, treeNode** root){ if (begin > end) return; else{ *root = (treeNode*) malloc(sizeof(treeNode)); int mid = (begin + end) / 2; (*root)->data = a[mid]; (*root)->rchild = NULL; (*root)->lchild = NULL; createTreeFromArray(a, begin ,mid - 1, &(*root)->lchild); createTreeFromArray(a, mid + 1 ,end, &(*root)->rchild); } } //問題8：判斷整數序列是不是二叉搜索樹的後//序遍歷結果 int isPostTraverse(int a[], int begin ,int end){ if(begin >= end) return 1; else{ int root = a[end]; int lroot; int i; int location = begin; for (i = begin; i < end ; i ++){ if(a[i] > root){ location = i; lroot = a[i]; break; } } for (i = location + 1; i < end; i++){ if (a[i] < lroot){ return 0; } } int flag1 = isPostTraverse(a,begin,location -1); int flag2 = isPostTraverse(a,location,end - 1); if (flag1 && flag2) return 1; else return 0; } } //問題9：求二叉樹的鏡像 void changeMirror(treeNode** root){ if ( *root == NULL) return; else{ treeNode* temp = (*root)->lchild; (*root)->lchild = (*root)->rchild; (*root)->rchild = temp; changeMirror(&(*root)->lchild); changeMirror(&(*root)->rchild); } } //問題10：10.一棵排序二叉樹（即二叉搜索樹BST），令 f=(最大值+最小值)/2，設計一個算 //法，找出距離f值最近、大於f值的結點。復雜度如果是O(n2)則不得分。 int findNearMid(treeNode** root){ treeNode* ptr = *root; int min, max; while (ptr != NULL){ min = ptr->data; ptr = ptr->lchild; } printf("the min is %d\n",min); ptr = *root; while (ptr != NULL){ max = ptr->data; ptr = ptr->rchild; } printf("the max is %d\n",max); int half = (min + max) >> 1; printf("half is %d\n",half); ptr = *root; while (1){ if (ptr->data < half){ ptr = ptr->rchild; } else if (ptr->data > half){ int result = ptr->data; return result; } else { return (ptr->rchild)->data; } } } //問題12：打印二叉樹中的所有路徑（與題目5很相似） void printPathsRecur(treeNode* node, int path[], int pathLen) { if (node == NULL) return; // append this node to the path array path[pathLen] = node->data; pathLen++; // it's a leaf, so print the path that led to here if (node->lchild == NULL && node->rchild == NULL) { printArray(path, pathLen); } else { // otherwise try both subtrees printPathsRecur(node->lchild, path, pathLen); printPathsRecur(node->rchild, path, pathLen); } } void printPaths(treeNode* node) { int path[1000]; printPathsRecur(node, path, 0); } //用到的輔助函數： /** * 求二叉樹的深度 */ int getDepth(tNode root) { if (root == NULL) return 0; else return getDepth(root->lchild) > getLeaf(root->rchild) ? 1 + getDepth( root->lchild) : 1 + getDepth(root->rchild); // { // int depthLchild = 1 + getDepth(root->lchild); // int depthRchild = 1 + getDepth(root->rchild); // return depthLchild > depthRchild ? depthLchild: depthRchild; // } } /** * 打印數組 */ void printArray(int ints[], int len) { int i; for (i = 0; i < len; i++) { printf("%d ", ints[i]); } printf("\n"); }
