題目

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

分析

根據(jù)樹的中序和后續(xù)，構(gòu)造出該二叉樹。先找出根節(jié)點，然后分析左右子樹。

/**
 * 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;
}