# Leetcode 106 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 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* dfs(vector<int>& preorder, int ps,int pe,vector<int>& inorder,int is,int ie)
{
if(ps>pe ) return NULL;
TreeNode* root=new TreeNode(preorder[pe]);
int pos;
for(int i=is;;i++)
if(inorder[i]==preorder[pe])
{
pos=ie-i;
break;
}
root->left=dfs(preorder,ps,pe-pos-1,inorder,is,ie-pos-1);
root->right=dfs(preorder,pe-pos,pe-1,inorder,ie-pos+1,ie);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return dfs(postorder,0,inorder.size()-1,inorder,0,inorder.size()-1);
}
};```

0 条评论

## 相关文章

21200

14630

83740

17040

27800

### GO语言 TCP传输实例

package main import ( "net" "fmt" ) var ( maxRead = 1100 msgStop = []byt...

35060

2.3K20

51140

50420

21650