前序中序遍歷構造二叉樹

思路

1. 在前序中找根結點
2. 根據根結點 + 中序，分成左右兩棵子樹
3. 根據子樹長度，把前序分成左右兩顆子樹
4. 遞歸處理子樹

/*** 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;}//從前序遍歷中找到根結點int rootValue = preorder[0];//根據根的值，在中序遍歷中找到其下標int rindex = -1;for (int i = 0; i < inorderSize; i++){//假設樹的結點不重復if (inorder[i] == rootValue){rindex = i;}}assert(rindex != -1);//創建根struct TreeNode* root = (struct TreeNode *)malloc(sizeof(struct TreeNode));root->val=rootValue;//創建左子樹root->left = buildTree(preorder+1,rindex,inorder,rindex);//創建右子樹root->right = buildTree(preorder+1+rindex,preorderSize-1-rindex,inorder+rindex+1,inorderSize-rindex-1);return root;
}