題目描述
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果走芋，請重建該二叉樹绩郎。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復的數(shù)字。
例如翁逞，給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：
限制：
0 <= 節(jié)點個數(shù) <= 5000
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
解題思路
前序遍歷的第一個節(jié)點即為該二叉樹的根節(jié)點肋杖，其后分別是左子樹節(jié)點和右子樹節(jié)點，但是前序遍歷無法區(qū)分左子樹和右子樹的分界挖函；中序遍歷的根節(jié)點在序列中間状植，根節(jié)點左側(cè)為左子樹節(jié)點，后側(cè)為右子樹節(jié)點，這樣結(jié)合前序遍歷和中序遍歷的根節(jié)點可以把原始序列分別劃分為左子樹和右子樹序列津畸，同樣振定，這兩段序列可以按照前面一樣的方法進行節(jié)點確認，最終能重建二叉樹肉拓。
代碼
/**
* 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){
if(preorderSize == 0) return NULL;
int index = 0;
struct TreeNode* pnode=malloc(sizeof(struct TreeNode));
pnode->val = preorder[0];
while(index < inorderSize)
{
if(inorder[index] == preorder[0]) break;
else index++;
}
pnode->left = buildTree(preorder + 1, index, inorder, index);
pnode->right = buildTree(preorder + 1 + index, preorderSize - index - 1, inorder + index + 1, preorderSize - index - 1);
return pnode;
}
執(zhí)行結(jié)果
