Leetcode Construct Binary Tree from Inorder and Postorder Traversal

时间:2023-01-18 06:28:46

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

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

class Solution {
public:
TreeNode *buildTree(vector<int>& inorder, int in_left,int in_right,
vector<int>& postorder, int post_left, int post_right){
if(in_right < in_left || post_right < post_left) return NULL;
TreeNode *root = new TreeNode(postorder[post_right]);
int index = in_left;
for( ; index <= in_right; ++ index ) if(inorder[index] == postorder[post_right]) break;
int right_cnt = in_right-index;
root->left = buildTree(inorder,in_left,index-,postorder,post_left,post_right-right_cnt-);
root->right = buildTree(inorder,index+,in_right,postorder, post_right-right_cnt,post_right-);
return root;
} TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
if(inorder.size() == ) return NULL;
else return buildTree(inorder,,inorder.size()-, postorder,,postorder.size()-);
}
};