前序中序遍歷構(gòu)造二叉樹

思路

在前序中找根結(jié)點(diǎn)

根據(jù)根結(jié)點(diǎn) + 中序，分成左右兩棵子樹

根據(jù)子樹長(zhǎng)度，把前序分成左右兩顆子樹

遞歸處理子樹

/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){assert(preorderSize == inorderSize);if (preorderSize == 0){return NULL;}//從前序遍歷中找到根結(jié)點(diǎn)int rootValue = preorder[0];//根據(jù)根的值，在中序遍歷中找到其下標(biāo)int rindex = -1;for (int i = 0; i < inorderSize; i++){//假設(shè)樹的結(jié)點(diǎn)不重復(fù)if (inorder[i] == rootValue){rindex = i;}}assert(rindex != -1);//創(chuàng)建根struct TreeNode* root = (struct TreeNode *)malloc(sizeof(struct TreeNode));root->val=rootValue;//創(chuàng)建左子樹root->left = buildTree(preorder+1,rindex,inorder,rindex);//創(chuàng)建右子樹root->right = buildTree(preorder+1+rindex,preorderSize-1-rindex,inorder+rindex+1,inorderSize-rindex-1);return root; }

總結(jié)

以上是生活随笔為你收集整理的二叉树题目 ----7 前序中序遍历构造二叉树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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