牛客网-剑指Offer-重建二叉树

题目链接：https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

前序遍历：根-左-右

中序遍历：左-根-右

后序遍历：左-右-根

遍历前序序列，每个元素找到它在中序序列中对应的位置，该位置左边代表左子树，右边代表右子树，递归建树

以样例为例，元素1，在中序序列中下标为3，所以0~2为左子树，4~7为右子树。

　　　　　　元素2，在中序序列中下标为2，所以0~1为左子树，没有右子树。

递归版：

 1 class Solution {
 2 public:
 3     
 4     int k;
 5     map<int, int> a;
 6     Solution()
 7     {
 8         k = 0;
 9     }
10     
11     void built(int l, int r, TreeNode* &cur, vector<int> &pre)
12     {
13         if(l > r)
14             return;
15 
16         cur = new TreeNode(pre[k]);
17         int t = k++;
18 
19         built(l, a[pre[t]] - 1, cur->left, pre);
20 
21         built(a[pre[t]] + 1, r, cur->right, pre);
22     }
23 
24     
25     TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
26         int len = pre.size();
27         for(int i = 0; i < len; i++)
28             a[vin[i]] = i;
29         
30         TreeNode* cur = NULL;
31         built(0, len - 1, cur, pre);
32         return cur;
33     }
34 };

View Code

非递归版：

 1 struct StackNode{
 2     TreeNode* cur;
 3     int l, r;
 4     int vis;
 5     StackNode(TreeNode *cur, int l, int r, int vis)
 6     {
 7         this->cur = cur;
 8         this->l = l;
 9         this->r = r;
10         this->vis = vis;
11     }
12 };
13 
14 class Solution {
15 public:
16 
17     int k;
18     map<int, int> a;
19     stack<StackNode* > s;
20     Solution()
21     {
22         k = 0;
23     }
24 
25     TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
26         int len = pre.size();
27         int pos = 0;
28         for(int i = 0; i < len; i++)
29             a[vin[i]] = i;
30 
31         TreeNode *cur = NULL;
32         if(!len)
33             return cur;
34         cur = new TreeNode(pre[pos++]);
35         StackNode *node = new StackNode(cur, 0, len - 1, 0);
36         s.push(node);
37         while(!s.empty())
38         {
39             node = s.top();
40             cur = node->cur;
41 
42             if(node->l < a[cur->val] && node->vis < 1)
43             {
44                 s.pop();
45                 node->vis = 1;
46                 s.push(node);
47                 cur->left = new TreeNode(pre[pos++]);
48                 node = new StackNode(cur->left, node->l, a[cur->val] - 1, 0);
49                 s.push(node);
50                 continue;
51             }
52 
53             if(node->r > a[cur->val] && node->vis < 2)
54             {
55                 s.pop();
56                 node->vis = 2;
57                 s.push(node);
58                 cur->right = new TreeNode(pre[pos++]);
59                 node = new StackNode(cur->right, a[cur->val] + 1, node->r, 0);
60                 s.push(node);
61                 continue;
62             }
63 
64             s.pop();
65         }
66         return cur;
67     }
68 };

View Code