首页 > 代码库 > Construct Binary Tree from Preorder and Inorder Traversal<leetcode>

Construct Binary Tree from Preorder and Inorder Traversal<leetcode>

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

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

题意:知道二叉树的前序遍历和中序遍历,重新构建出二叉树。

算法:(略),代码如下:

 1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {13         if(preorder.empty()||inorder.empty())  return NULL;14         return build(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);15     }16     TreeNode  *build(vector<int> &preorder,int l,int r,vector<int> &inorder,int ll,int rr)17     {18         if(l>r||ll>rr)  return NULL;19         TreeNode* root=new TreeNode(0);20         root->val=preorder[l];21         if(l==r)  return root;22         int mid=0;23         for(int i=ll;i<=rr;i++)24         {25             if(inorder[i]==preorder[l])26             {27                 mid=i;28                 break;29             }30         }31         int midd=mid-ll+l;32         root->left=build(preorder,l+1,midd,inorder,ll,mid-1);33         root->right=build(preorder,midd+1,r,inorder,mid+1,rr);34         return root;35     }36 };

 

Construct Binary Tree from Preorder and Inorder Traversal<leetcode>