题目
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
分析
根据树的中序和后续，构造出该二叉树。先找出根节点，然后分析左右子树。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {
if(inorderSize==0)
return NULL;
int root=postorder[postorderSize-1];
struct TreeNode *tree=(struct TreeNode*)malloc(sizeof(struct TreeNode));
tree->val=root;
int i;
for(i=0;i<inorderSize;i++)
if(inorder[i]==root)
break;
tree->left=buildTree(inorder,i,postorder,i);
tree->right=buildTree(inorder+i+1,inorderSize-i-1,postorder+i,inorderSize-i-1);
return tree;
}
