首页 > 代码库 > 【LeetCode】Construct Binary Tree from Inorder and Postorder Traversal

【LeetCode】Construct Binary Tree from Inorder and Postorder Traversal

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 binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
   struct TreeNode {         int val;         TreeNode *left;         TreeNode *right;         TreeNode(int x) : val(x), left(NULL), right(NULL) {}     };TreeNode *build(vector<int> &inorder, int st_i,int end_i , vector<int> &postorder, int st_p, int end_p){    if (st_i == end_i)//this tree contains only one node    {        TreeNode *root = new TreeNode(inorder[st_i]);        return root;    }    TreeNode *root = new TreeNode(postorder[end_p]);    int left_len = 0;    for (int i = st_i; i <= end_i; i++)    {        if (inorder[i] == postorder[end_p])//find the root node        {            left_len = i-st_i;            break;        }    }    if (left_len > 0)//left subtree exist    {        root->left = build(inorder, st_i, left_len+st_i-1, postorder, st_p, st_p+left_len-1);    }    if (st_i+left_len < end_i)//right subtree exist    {        root->right = build(inorder, st_i+left_len+1, end_i, postorder, st_p+left_len, end_p-1);    }    return root;}TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder){    if (inorder.size() == 0 || postorder.size() == 0)    {        return NULL;    }    TreeNode *root = new TreeNode(postorder.back());    int left_child_length = 0;    for (int i = 0; i < inorder.size(); i++)    {        if (postorder.back() == inorder[i])        {            left_child_length = i;            break;        }    }    if (left_child_length > 0)    {        root->left = build(inorder, 0, left_child_length-1, postorder, 0, left_child_length -1);    }    if (left_child_length < inorder.size()-1)    {        root->right = build(inorder, left_child_length + 1, inorder.size()-1, postorder, left_child_length, postorder.size()-2);    }    return root;}
};