0%

LeetCode-Construct Binary Tree from Inorder and Postorder Traversal

https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

和上一题Construct Binary Tree from Preorder and Inorder Traversal思路几乎一模一样,在此不多赘述。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* build(vector<int>& inorder, vector<int>& postorder, int in_l, int in_r, int post_l, int post_r) {
if(in_l>in_r || post_l>post_r) return nullptr;
int root_val = postorder[post_r];
TreeNode* root = new TreeNode(root_val);
int in_split_pos = in_r;
for(int i=in_r; i>=in_l; --i) {
if(inorder[i] == root_val) {
in_split_pos = i;
break;
}
}
int diff = in_r - in_split_pos;
root->right = build(inorder, postorder, in_split_pos+1, in_r, post_r-diff, post_r-1);
root->left = build(inorder, postorder, in_l, in_split_pos-1, post_l, post_r-diff-1);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int len = inorder.size();
if(len==0) return nullptr;
return build(inorder, postorder, 0, len-1, 0, len-1);
}
};