好贷网好贷款

[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal

发布时间:2016-12-5 12:38:44 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal",主要涉及到[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal方面的内容,对于[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal感兴趣的同学可以参考一下。

Construct Binary Tree from Preorder and Inorder Traversal: Given preorder and inorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. 注意没有重复元素很重要,如果有重复元素的话,需要在寻找pos的时候对每个pos都尝试一下 /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) { // Start typing your C/C++ solution below // DO NOT write int main() function int psz=preorder.size(),isz=inorder.size(); assert(psz==isz); return create(preorder,0,psz-1,inorder,0,isz-1); } TreeNode* create(vector<int>& pre,int pl,int pr,vector<int>& in,int il,int ir) { if ( pl>pr ) { assert(il>ir); return NULL; } int val=pre[pl]; int pos=il; for(;pos<=ir;pos++) if ( in[pos]==val) break; assert(pos<=ir); TreeNode* root=new TreeNode(val); int ln=pos-il; int rn=ir-pos; root->left=create(pre,pl+1,pl+ln,in,il,pos-1); root->right=create(pre,pl+ln+1,pr,in,pos+1,ir); return root; } };

上一篇:变态鹦鹉笑话全集
下一篇:C++函数头文件

相关文章

相关评论