Given preorder and inorder 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* buildhelp(vector<int>& preorder, vector<int>& inorder,int pStart,int pEnd,int iStart,int iEnd){if(pStart>pEnd||iStart>iEnd)return NULL;TreeNode *Tnode=new TreeNode(preorder[pStart]);if(pStart==pEnd)return Tnode;int cur=iStart;while(inorder[cur]!=preorder[pStart])cur++; Tnode->left=buildhelp(preorder, inorder,pStart+1,pStart+(cur-iStart),iStart,cur-1); Tnode->right=buildhelp(preorder, inorder,pEnd-(iEnd-cur-1),pEnd,cur+1,iEnd);return Tnode; }TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {TreeNode* Tree=NULL;if(preorder.size()==0)return Tree;Tree=buildhelp(preorder, inorder,0,preorder.size()-1,0,inorder.size()-1);return 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* buildhelp(vector<int>& preorder, vector<int>& inorder,int pStart,int pEnd,int iStart,int iEnd){if(pStart<pEnd||iStart<iEnd)return NULL;TreeNode Tnode(preorder[pStart]);if(pStart==pEnd)return &Tnode;int cur=iStart;while(inorder[cur]!=preorder[pStart])cur++; Tnode.left=buildhelp(preorder, inorder,pStart+1,pStart+(cur-iStart),iStart,cur-1); Tnode.right=buildhelp(preorder, inorder,pEnd-(iEnd-cur-1),pEnd,cur+1,iEnd);return &Tnode; }TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {TreeNode* Tree=NULL;if(preorder.size()==0)return Tree;Tree=buildhelp(preorder, inorder,0,preorder.size()-1,0,inorder.size()-1);return Tree;}};不同的地方在于 TreeNode Tnode(preorder[pStart]);然后返回其指针
这里犯了一个很大的错误就是，其实每次算法在遇到该处时候只是将结构体中的成员变量替换成了新的，，却没有构建新的节点。
为了验证我们的想法：
#include<iostream>#include<vector>using namespace std; struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {} };int main(){int i=5; while(i–) { TreeNode aa(i); cout<<&aa<<endl; }}我们在一个ｗｈｉｌｅ中多次重建该结构体但是其地址都没有发生改变
最后是第二道类似的算法
Construct Binary Tree from Inorder and Postorder TraversalTotal Accepted:32565Total Submissions:121341My Submissions
QuestionSolution
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:You may assume that duplicates do not exist in the tree.
<pre name="code" class="cpp">class Solution {public:TreeNode* buildhelp(vector<int>& inorder, vector<int>& postorder,int iStart,int iEnd,int pStart,int pEnd){if(pStart>pEnd||iStart>iEnd)return NULL;TreeNode *Tnode=new TreeNode(postorder[pEnd]);if(pStart==pEnd)return Tnode;int cur=iStart;while(inorder[cur]!=postorder[pEnd])cur++; Tnode->left=buildhelp(inorder, postorder,iStart,cur-1,pStart,pStart+(cur-iStart-1)); Tnode->right=buildhelp(inorder, postorder,cur+1,iEnd,pEnd-1-(iEnd-cur-1),pEnd-1);return Tnode; }TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if(inorder.size()==0)return NULL;return buildhelp(inorder, postorder,0,inorder.size()-1,0,postorder.size()-1);}};
每一件事都要用多方面的角度来看它
