首页 > 其他 > 详细

【树】105. 从前序与中序遍历序列构造二叉树

时间:2020-05-02 14:23:50      阅读:56      评论:0      收藏:0      [点我收藏+]

题目:

技术分享图片

 

 

 

解答:

递归求解。

基本情况:先序与中序数组长度小于1时,返回NULL。

递归步骤:首先去欸的那个preorder的第一个元素一定是该树的root,再在inorder中找到该元素,标记为index,index左部分为左子树的中序,右部分为右子树的中序;随后,通过左右子树中序的长度(可能为0),在preorder中确定左右子树的先序。

 1 /**
 2  * Definition for a binary tree node.
 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     
13     TreeNode *buildTreeHelper(vector<int>& preorder, int ps, int pe, vector<int>& inorder, int is, int ie)
14     {
15         if ((pe - ps < 0)  || (pe - ps) != (ie - is))
16         {
17             return NULL;
18         } 
19 
20         TreeNode *root = new TreeNode(preorder[ps]);
21 
22         int index = -1;
23         for (int i = is; i <= ie; i++)
24         {
25             if (inorder[i] == root->val)
26             {
27                 index = i;
28                 break;
29             }
30         }
31 
32         if (index == -1)
33         {
34             return root;
35         }
36 
37         int leftprelen = index - is;
38         root->left = buildTreeHelper(preorder, ps + 1, ps + leftprelen, inorder, is, index - 1);
39         root-> right = buildTreeHelper(preorder, ps + leftprelen + 1, pe, inorder, index + 1, ie);
40 
41         return root;
42     }
43 
44     TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
45     {
46         return buildTreeHelper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);    
47     }
48 };

 

【树】105. 从前序与中序遍历序列构造二叉树

原文:https://www.cnblogs.com/ocpc/p/12817672.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!