如題：

根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹。 注意: 你可以假設(shè)樹中沒有重復(fù)的元素。例如，給出 前序遍歷 preorder =?[3,9,20,15,7] 中序遍歷 inorder = [9,3,15,20,7] 返回如下的二叉樹：3/ \9 20/ \15 7

套路題，考察你有沒有學(xué)習(xí)過這種題型。同樣的問題還有知道中序與后序構(gòu)造二叉樹(leetcode 106)。我們知道，前序遍歷所得序列從左至右依次是：根節(jié)點，跟左子樹根節(jié)點.....右子樹根節(jié)點。和后序正好相反，后序遍歷所得序列從后往前依次是根節(jié)點，根右子樹根節(jié)點...左子樹根節(jié)點。因為題目保證沒有重復(fù)數(shù)字，知道了根節(jié)點，就可以從中序遍歷中找到對應(yīng)下標i，根據(jù)中序遍歷性質(zhì)，i左邊的數(shù)列表示左子樹，i右邊的數(shù)列表示右子樹。這樣，我們知道了根結(jié)點后，遞歸從中序數(shù)列中分別查找左子樹的根結(jié)點和右子樹根結(jié)點即可。

示例中給出的前序遍歷數(shù)列為【3，9，20，15，7】，由下面的二叉樹可以觀察到，結(jié)點3為根結(jié)點，9為3的左子樹根結(jié)點，20為3右子樹根結(jié)點。15為20左子樹根結(jié)點，7為20右子樹根結(jié)點。遞歸查找順序由此可得，先左子樹后右子樹。總的來說就是找根結(jié)點的過程。沒有看懂的同學(xué)可以結(jié)合下面的代碼看下：

//這道題和已知中序于后序遍歷求二叉樹類似，僅僅方向不同，遞歸求解即可 struct TreeNode *findSubRoot(int* preorder, int* inorder, int *preOrderEnd, int inStart, int inEnd) {int i, val;struct TreeNode *root, *left, *right;//中序序列找不到，說明是一個空節(jié)點if (inStart > inEnd)return NULL;//從前序遍歷中取出根節(jié)點的值val = preorder[*preOrderEnd];//指向下一個子樹的根節(jié)點*preOrderEnd = *preOrderEnd + 1;//找到val節(jié)點的左子樹和右子樹范圍for (i = 0; i <= inEnd; i++)if (inorder[i] == val)break;//找到val的左子樹與右子樹，順序不能反，先左后右left = findSubRoot(preorder, inorder, preOrderEnd, inStart, i - 1);right = findSubRoot(preorder, inorder, preOrderEnd, i + 1, inEnd);//組合root = (struct TreeNode *)calloc(1, sizeof(struct TreeNode));root->val = val;root->left = left;root->right = right;return root; }struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){//前序遍歷從前往后依次是根結(jié)點int preOrderEnd = 0;return findSubRoot(preorder, inorder, &preOrderEnd, 0, inorderSize - 1); }

?

=============================================================================================

Linux應(yīng)用程序、內(nèi)核、驅(qū)動開發(fā)交流討論群(745510310)，感興趣的同學(xué)可以加群討論、交流、資料查找等，前進的道路上，你不是一個人奧^_^。

總結(jié)

以上是生活随笔為你收集整理的leetcode 105. 从前序与中序遍历序列构造二叉树 c语言递归解法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。