LeetCode:105_Construct Binary Tree from Preorder and Inorder Traversal | 根据前序和中序遍历构建二叉树 | Medium

要求:通过二叉树的前序和中序遍历序列构建一颗二叉树

代码如下:

 1 struct TreeNode {
 2     int            val;
 3     TreeNode    *left;
 4     TreeNode    *right;
 5     TreeNode(int x): val(x),left(NULL), right(NULL) {}
 6 };
 7 
 8 typedef vector<int>::iterator Iter;
 9 TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) 
10 {
11     return buildTreeRecur(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
12 }
13 
14 TreeNode *buildTreeRecur(Iter pstart, Iter pend, Iter istart, Iter iend)
15 {
16     if(pstart == pend || istart == iend)
17         return NULL;
18     int ival = *pstart;
19     Iter ipos = find(istart, iend, ival);
20     TreeNode *res = new TreeNode(ival);
21     res->left = buildTreeRecur(pstart + 1, pstart+1+(ipos-istart), istart, ipos);
22     res->right = buildTreeRecur(pstart+1+(ipos-istart), pend, ipos+1, iend);
23     return res;
24 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励