Construct Binary Tree from Inorder and Postorder Traversal
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.
思路
根据中序和后序遍历建树，建立根节点，划分左子树和右子树。递归
解题
c++版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/**
* 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* buildTree(vector<int>& inorder, vector<int>& postorder) {
return solve(inorder,0,inorder.size()-1,postorder,postorder.size()-1);
}
TreeNode* solve(vector<int>& inorder,int low,int high,vector<int>& postorder,int p){
if(low>high)
return NULL;
TreeNode * root=new TreeNode(postorder[p]);
int pos=0;
for(int i=low;i<=high;++i){
if(postorder[p]==inorder[i]){
pos=i;
break;
}
}
root->left=solve(inorder,low,pos-1,postorder,p-high+pos-1);
root->right=solve(inorder,pos+1,high,postorder,p-1);
return root;
}
};
python版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# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param {integer[]} inorder
# @param {integer[]} postorder
# @return {TreeNode}
def buildTree(self, inorder, postorder):
return self.solve(inorder,0,len(inorder)-1,postorder,len(postorder)-1)
def solve(self,inorder,low,high,postorder,p):
if low>high:
return None
root=TreeNode(postorder[p])
for i in range(low,high+1):
if postorder[p]==inorder[i]:
pos=i
break
root.left=self.solve(inorder,low,pos-1,postorder,p-high+pos-1)
root.right=self.solve(inorder,pos+1,high,postorder,p-1)
return root
