分享我的Lintcode题解，目前进度244/248

Merge Sorted Array
题意：归并两个有序数组A和B到A中，假设A的空间充足。
解法：对之前的归并代码稍作修改。
代码：

1. #include <algorithm>
   
2. using namespace std;
   
3. 
   
4. class Solution {
   
5. public:
   
6.     /**
   
7.      * @param A: sorted integer array A which has m elements,
   
8.      *           but size of A is m+n
   
9.      * @param B: sorted integer array B which has n elements
   
10.      * @return: void
    
11.      */
    
12.     void mergeSortedArray(int A[], int m, int B[], int n) {
    
13.         int i, j, k;
    
14.         
    
15.         i = m - 1;
    
16.         j = n - 1;
    
17.         k = m + n - 1;
    
18.         while (i >= 0 && j >= 0) {
    
19.             if (A[i] > B[j]) {
    
20.                 A[k--] = A[i--];
    
21.             } else {
    
22.                 A[k--] = B[j--];
    
23.             }
    
24.         }
    
25.         while (j >= 0) {
    
26.             A[k--] = B[j--];
    
27.         }
    
28.     }
    
29. };

复制代码

复杂度：时间O(N + M)，空间O(1)

Median of two Sorted Arrays
题意：hard难度。给定两个有序数组，求出把两者归并以后的新数组的中位数。
解法：这题用线性复杂度肯定容易做，就不写了。挑战性在于对数复杂度。这题首先要考虑的问题是“求归并数组中第K小的元素”。我的思路类似于快速选择算法，不过搜索范围在俩数组里，所以要逐步缩小两个数组中的搜索范围。直到其中一个数组被完全排除为止。代码比较复杂，因为写的时候思路并不清晰，磕磕绊绊的。
代码：

1. // O(log(m) * log(n)) solution
   
2. #include <algorithm>
   
3. using namespace std;
   
4. 
   
5. typedef vector<int> VI;
   
6. class Solution {
   
7. public:
   
8.     /**
   
9.      * @param A: An integer array.
   
10.      * @param B: An integer array.
    
11.      * @return: a double whose format is *.5 or *.0
    
12.      */
    
13.     double findMedianSortedArrays(VI A, VI B) {
    
14.         na = A.size();
    
15.         nb = B.size();
    
16.         if ((na + nb) % 2) {
    
17.             return kthSmallest(A, B, 0, na - 1, 0, nb - 1, (na + nb) / 2);
    
18.         } else {
    
19.             int a1 = kthSmallest(A, B, 0, na - 1, 0, nb - 1, (na + nb - 1) / 2);
    
20.             int a2 = kthSmallest(A, B, 0, na - 1, 0, nb - 1, (na + nb) / 2);
    
21.             return (a1 + a2) / 2.0;
    
22.         }
    
23.     }
    
24. private:
    
25.     int na, nb;
    
26.    
    
27.     int kthSmallest(VI &a, VI &b, int la, int ra, int lb, int rb, int k) {
    
28.         if (la > ra) {
    
29.             return b[lb + k];
    
30.         }
    
31.         if (lb > rb) {
    
32.             return a[la + k];
    
33.         }
    
34.         if (a[ra] <= b[lb]) {
    
35.             return k <= ra - la ? a[la + k] : b[lb + k - (ra - la + 1)];
    
36.         }
    
37.         if (b[rb] <= a[la]) {
    
38.             return k <= rb - lb ? b[lb + k] : a[la + k - (rb - lb + 1)];
    
39.         }
    
40.         int ma = la + (ra - la) / 2;
    
41.         int mb = lower_bound(b.begin() + lb, b.begin() + rb + 1, a[ma]) - b.begin();
    
42.         if (b[mb] > a[ma]) {
    
43.             --mb;
    
44.         }
    
45.         int cc = (ma - la) + 1 + (mb - lb) + 1;
    
46.         if (k + 1 < cc) {
    
47.             return kthSmallest(a, b, la, ma - 1, lb, mb, k);
    
48.         } else if (k + 1 > cc) {
    
49.             return kthSmallest(a, b, ma + 1, ra, mb + 1, rb, k - cc);
    
50.         } else {
    
51.             return a[ma];
    
52.         }
    
53.     }
    
54. };

复制代码

复杂度：题目提示时间复杂度可以到O(log(N + M))，而我的代码只做到了O(log(N) * log(M))，空间也一样。谁有更简洁高效的，不妨分享一下？

Binary Tree Preorder Traversal
题意：二叉树的前序遍历。
解法1：递归
代码1：

1. /**
   
2. * Definition of TreeNode:
   
3. * class TreeNode {
   
4. * public:
   
5. *     int val;
   
6. *     TreeNode *left, *right;
   
7. *     TreeNode(int val) {
   
8. *         this->val = val;
   
9. *         this->left = this->right = NULL;
   
10. *     }
    
11. * }
    
12. */
    
13. 
    
14. class Solution {
    
15. public:
    
16.     /**
    
17.      * @param root: The root of binary tree.
    
18.      * @return: Preorder in vector which contains node values.
    
19.      */
    
20.     vector<int> preorderTraversal(TreeNode *root) {
    
21.                 ans.clear();
    
22.                 traverse(root);
    
23.                 return ans;
    
24.     }
    
25. private:
    
26.         vector<int> ans;
    
27.        
    
28.         void traverse(TreeNode *root) {
    
29.                 if (root == NULL) {
    
30.                         return;
    
31.                 }
    
32.                 ans.push_back(root->val);
    
33.                 traverse(root->left);
    
34.                 traverse(root->right);
    
35.         }
    
36. };

复制代码

复杂度1：时间O(N)，空间O(N)。

解法2：用栈代替。Morris遍历还不会，会了之后我再补上。
代码2：

1. // The iterative version
   
2. #include <stack>
   
3. using namespace std;
   
4. /**
   
5. * Definition of TreeNode:
   
6. * class TreeNode {
   
7. * public:
   
8. *     int val;
   
9. *     TreeNode *left, *right;
   
10. *     TreeNode(int val) {
    
11. *         this->val = val;
    
12. *         this->left = this->right = NULL;
    
13. *     }
    
14. * }
    
15. */
    
16. 
    
17. class Solution {
    
18. public:
    
19.     /**
    
20.      * @param root: The root of binary tree.
    
21.      * @return: Preorder in vector which contains node values.
    
22.      */
    
23.     vector<int> preorderTraversal(TreeNode *root) {
    
24.         vector<int> ans;
    
25.         if (root == NULL) {
    
26.             return ans;
    
27.         }
    
28.         
    
29.         stack<TreeNode *> st;
    
30.         TreeNode *p;
    
31.         p = root;
    
32.         while (true) {
    
33.             while (p != NULL) {
    
34.                 ans.push_back(p->val);
    
35.                 st.push(p);
    
36.                 p = p->left;
    
37.             }
    
38.             while (!st.empty() && st.top()->right == NULL) {
    
39.                 st.pop();
    
40.             }
    
41.             if (st.empty()) {
    
42.                 break;
    
43.             }
    
44.             p = st.top()->right;
    
45.             st.pop();
    
46.         }
    
47.         return ans;
    
48.     }
    
49. };

复制代码

复杂度2：时间O(N)，空间O(N)。

Binary Tree Inorder Traversal
题意：二叉树的中序遍历。
解法1：递归
代码1：

1. /**
   
2. * Definition of TreeNode:
   
3. * class TreeNode {
   
4. * public:
   
5. *     int val;
   
6. *     TreeNode *left, *right;
   
7. *     TreeNode(int val) {
   
8. *         this->val = val;
   
9. *         this->left = this->right = NULL;
   
10. *     }
    
11. * }
    
12. */
    
13. class Solution {
    
14.     /**
    
15.      * @param root: The root of binary tree.
    
16.      * @return: Inorder in vector which contains node values.
    
17.      */
    
18. public:
    
19.     vector<int> inorderTraversal(TreeNode *root) {
    
20.                 ans.clear();
    
21.                 traverse(root);
    
22.                 return ans;
    
23.     }
    
24. private:
    
25.         vector<int> ans;
    
26.        
    
27.         void traverse(TreeNode *root) {
    
28.                 if (root == NULL) {
    
29.                         return;
    
30.                 }
    
31.                 traverse(root->left);
    
32.                 ans.push_back(root->val);
    
33.                 traverse(root->right);
    
34.         }
    
35. };

复制代码

复杂度1：时间O(N)，空间O(N)。

解法2：用栈代替递归。
代码2：

1. #include <stack>
   
2. using namespace std;
   
3. /**
   
4. * Definition of TreeNode:
   
5. * class TreeNode {
   
6. * public:
   
7. *     int val;
   
8. *     TreeNode *left, *right;
   
9. *     TreeNode(int val) {
   
10. *         this->val = val;
    
11. *         this->left = this->right = NULL;
    
12. *     }
    
13. * }
    
14. */
    
15. class Solution {
    
16.     /**
    
17.      * @param root: The root of binary tree.
    
18.      * @return: Inorder in vector which contains node values.
    
19.      */
    
20. public:
    
21.     vector<int> inorderTraversal(TreeNode *root) {
    
22.         vector<int> ans;
    
23.         if (root == NULL) {
    
24.             return ans;
    
25.         }
    
26.         stack<TreeNode *> st;
    
27.         TreeNode *p;
    
28.         p = root;
    
29.         while (true) {
    
30.             while (p != NULL) {
    
31.                 st.push(p);
    
32.                 p = p->left;
    
33.             }
    
34.             while (!st.empty() && st.top()->right == NULL) {
    
35.                 ans.push_back(st.top()->val);
    
36.                 st.pop();
    
37.             }
    
38.             if (st.empty()) {
    
39.                 break;
    
40.             }
    
41.             p = st.top()->right;
    
42.             ans.push_back(st.top()->val);
    
43.             st.pop();
    
44.         }
    
45.         return ans;
    
46.     }
    
47. };

复制代码

复杂度2：时间O(N)，空间O(N)。

Binary Tree Postorder Traversal
题意：二叉树的后序遍历。
解法1：递归
代码1：

1. /**
   
2. * Definition of TreeNode:
   
3. * class TreeNode {
   
4. * public:
   
5. *     int val;
   
6. *     TreeNode *left, *right;
   
7. *     TreeNode(int val) {
   
8. *         this->val = val;
   
9. *         this->left = this->right = NULL;
   
10. *     }
    
11. * }
    
12. */
    
13. 
    
14. class Solution {
    
15. public:
    
16.     /**
    
17.      * @param root: The root of binary tree.
    
18.      * @return: Postorder in vector which contains node values.
    
19.      */
    
20.     vector<int> postorderTraversal(TreeNode *root) {
    
21.                 ans.clear();
    
22.                 traverse(root);
    
23.                 return ans;
    
24.     }
    
25. private:
    
26.         vector<int> ans;
    
27.        
    
28.         void traverse(TreeNode *root) {
    
29.                 if (root == NULL) {
    
30.                         return;
    
31.                 }
    
32.                 traverse(root->left);
    
33.                 traverse(root->right);
    
34.                 ans.push_back(root->val);
    
35.         }
    
36. };

复制代码

复杂度1：时间O(N)，空间O(N)。

解法2：用栈代替递归，这个更复杂些。
代码2：

1. #include <stack>
   
2. using namespace std;
   
3. /**
   
4. * Definition of TreeNode:
   
5. * class TreeNode {
   
6. * public:
   
7. *     int val;
   
8. *     TreeNode *left, *right;
   
9. *     TreeNode(int val) {
   
10. *         this->val = val;
    
11. *         this->left = this->right = NULL;
    
12. *     }
    
13. * }
    
14. */
    
15. class Solution {
    
16.     /**
    
17.      * @param root: The root of binary tree.
    
18.      * @return: Postorder in vector which contains node values.
    
19.      */
    
20. public:
    
21.     vector<int> postorderTraversal(TreeNode *root) {
    
22.         vector<int> ans;
    
23.         if (root == NULL) {
    
24.             return ans;
    
25.         }
    
26.         stack<TreeNode *> st;
    
27.         TreeNode *p = root, *oldp;
    
28.         while (true) {
    
29.             while (p != NULL) {
    
30.                 st.push(p);
    
31.                 p = p->left;
    
32.             }
    
33.             while (!st.empty() && st.top()->right == NULL) {
    
34.                 ans.push_back(st.top()->val);
    
35.                 oldp = st.top();
    
36.                 st.pop();
    
37.             }
    
38.             while (!st.empty() && oldp == st.top()->right) {
    
39.                 ans.push_back(st.top()->val);
    
40.                 oldp = st.top();
    
41.                 st.pop();
    
42.             }
    
43.             if (st.empty()) {
    
44.                 break;
    
45.             }
    
46.             p = st.top()->right;
    
47.         }
    
48.         return ans;
    
49.     }
    
50. };

复制代码

复杂度2：时间O(N)，空间O(N)。

Binary Tree Level Order Traversal
题意：二叉树的层次遍历，不过这题要求结果按行分开存放。所以跟平时所说的层次遍历不一样。
解法：照理说应该是用BFS来做，但这题要求按行分开存结果，所以我改成递归的前序遍历了。
代码：

1. /**
   
2. * Definition of TreeNode:
   
3. * class TreeNode {
   
4. * public:
   
5. *     int val;
   
6. *     TreeNode *left, *right;
   
7. *     TreeNode(int val) {
   
8. *         this->val = val;
   
9. *         this->left = this->right = NULL;
   
10. *     }
    
11. * }
    
12. */
    
13. class Solution {
    
14.     /**
    
15.      * @param root: The root of binary tree.
    
16.      * @return: Level order a list of lists of integer
    
17.      */
    
18. public:
    
19.     vector<vector<int> > levelOrder(TreeNode *root) {
    
20.         ans.clear();
    
21.         if (root == NULL) {
    
22.             return ans;
    
23.         }
    
24.         preorder(root, 0);
    
25.         return ans;
    
26.     }
    
27. private:
    
28.     vector<vector<int> > ans;
    
29.    
    
30.     void preorder(TreeNode *root, int depth) {
    
31.         if (depth + 1 > ans.size()) {
    
32.             ans.push_back(vector<int>());
    
33.         }
    
34.         ans[depth].push_back(root->val);
    
35.         if (root->left != NULL) {
    
36.             preorder(root->left, depth + 1);
    
37.         }
    
38.         if (root->right != NULL) {
    
39.             preorder(root->right, depth + 1);
    
40.         }
    
41.     }
    
42. };

复制代码

复杂度：时间O(N)，空间O(N)。

Binary Tree Level Order Traversal II
题意：依然是层次遍历，依然是按行分开存，不过这会要求上下颠倒。
解法：感觉比较无聊，既可以搞定以后一口气反转。也可以在遍历的过程中就按照行反序来保存结果。
代码：

1. #include <algorithm>
   
2. using namespace std;
   
3. /**
   
4. * Definition of TreeNode:
   
5. * class TreeNode {
   
6. * public:
   
7. *     int val;
   
8. *     TreeNode *left, *right;
   
9. *     TreeNode(int val) {
   
10. *         this->val = val;
    
11. *         this->left = this->right = NULL;
    
12. *     }
    
13. * }
    
14. */
    
15. class Solution {
    
16.     /**
    
17.      * @param root : The root of binary tree.
    
18.      * @return : buttom-up level order a list of lists of integer
    
19.      */
    
20. public:
    
21.     vector<vector<int> > levelOrderBottom(TreeNode *root) {
    
22.         if (root == NULL) {
    
23.             return ans;
    
24.         }
    
25.         maxDepth = 0;
    
26.         calcDepth(root, 1);
    
27.         ans.resize(maxDepth);
    
28.         preorder(root, 0);
    
29.         return ans;
    
30.     }
    
31. private:
    
32.     vector<vector<int> > ans;
    
33.     int maxDepth;
    
34.    
    
35.     void calcDepth(TreeNode *root, int depth) {
    
36.         maxDepth = max(maxDepth, depth);
    
37.         if (root->left != NULL) {
    
38.             calcDepth(root->left, depth + 1);
    
39.         }
    
40.         if (root->right != NULL) {
    
41.             calcDepth(root->right, depth + 1);
    
42.         }
    
43.     }
    
44.    
    
45.     void preorder(TreeNode *root, int depth) {
    
46.         ans[maxDepth - 1 - depth].push_back(root->val);
    
47.         if (root->left != NULL) {
    
48.             preorder(root->left, depth + 1);
    
49.         }
    
50.         if (root->right != NULL) {
    
51.             preorder(root->right, depth + 1);
    
52.         }
    
53.     }
    
54. };

复制代码

复杂度：时间O(N)，空间O(N)。

Binary Tree Zigzag Level Order Traversal
题意：和之前的层次遍历类似，不过这回要求每隔一行就把当前行给反过来。
解法：按照老办法，遍历完了再反转。
代码：

1. #include <algorithm>
   
2. using namespace std;
   
3. /**
   
4. * Definition of TreeNode:
   
5. * class TreeNode {
   
6. * public:
   
7. *     int val;
   
8. *     TreeNode *left, *right;
   
9. *     TreeNode(int val) {
   
10. *         this->val = val;
    
11. *         this->left = this->right = NULL;
    
12. *     }
    
13. * }
    
14. */
    
15. class Solution {
    
16.     /**
    
17.      * @param root: The root of binary tree.
    
18.      * @return: A list of lists of integer include
    
19.      *          the zigzag level order traversal of its nodes' values
    
20.      */
    
21. public:
    
22.     vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
    
23.         ans.clear();
    
24.         if (root == NULL) {
    
25.             return ans;
    
26.         }
    
27.         preorder(root, 0);
    
28.         int i;
    
29.         for (i = 1; i < ans.size(); i += 2) {
    
30.             reverse(ans[i].begin(), ans[i].end());
    
31.         }
    
32.         return ans;
    
33.     }
    
34. private:
    
35.     vector<vector<int> > ans;
    
36.    
    
37.     void preorder(TreeNode *root, int depth) {
    
38.         if (depth + 1 > ans.size()) {
    
39.             ans.push_back(vector<int>());
    
40.         }
    
41.         ans[depth].push_back(root->val);
    
42.         if (root->left != NULL) {
    
43.             preorder(root->left, depth + 1);
    
44.         }
    
45.         if (root->right != NULL) {
    
46.             preorder(root->right, depth + 1);
    
47.         }
    
48.     }
    
49. };

复制代码

复杂度：时间O(N)，空间O(N)。

Construct Binary Tree from Inorder and Postorder Traversal
题意：给定中序和后序遍历，请重建一棵二叉树。
解法1：用递归的方法重建，找出根节点的位置。
代码1：

1. /**
   
2. * Definition of TreeNode:
   
3. * class TreeNode {
   
4. * public:
   
5. *     int val;
   
6. *     TreeNode *left, *right;
   
7. *     TreeNode(int val) {
   
8. *         this->val = val;
   
9. *         this->left = this->right = NULL;
   
10. *     }
    
11. * }
    
12. */
    
13. class Solution {
    
14.     /**
    
15.      *@param inorder : A list of integers that inorder traversal of a tree
    
16.      *@param postorder : A list of integers that postorder traversal of a tree
    
17.      *@return : Root of a tree
    
18.      */
    
19. public:
    
20.     TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
    
21.         int n = inorder.size();
    
22.         if (n == 0) {
    
23.             return NULL;
    
24.         }
    
25.         return construct(inorder, postorder, 0, n - 1, 0, n - 1);
    
26.     }
    
27. private:
    
28.     TreeNode *construct(vector<int> &in, vector<int> &post,
    
29.                         int ill, int irr, int pll, int prr) {
    
30.         int rootVal = post[prr];
    
31.         TreeNode *r = new TreeNode(rootVal);
    
32.         int i;
    
33.         for (i = ill; i <= irr; ++i) {
    
34.             if (in[i] == rootVal) {
    
35.                 break;
    
36.             }
    
37.         }
    
38.         int len;
    
39.         if (i > ill) {
    
40.             len = i - ill;
    
41.             r->left = construct(in, post, ill, i - 1, pll, pll + len - 1);
    
42.         }
    
43.         if (i < irr) {
    
44.             len = irr - i;
    
45.             r->right = construct(in, post, i + 1, irr, prr - len, prr - 1);
    
46.         }
    
47.         return r;
    
48.     }
    
49. };

复制代码

复杂度1：时间平均为O(N * log(N))，最坏可以变成O(N ^ 2)，空间是O(N)。

解法2：因为节点中不存在重复的值，所以借助hashing可以在O(1)时间找到根节点的位置。于是总体复杂度降到了O(N)。其实就算有重复的值，也可以用类似的思路实现，不过代码会更难写就是了。
代码2：

1. // Make it faster with hashing.
   
2. /**
   
3. * Definition of TreeNode:
   
4. * class TreeNode {
   
5. * public:
   
6. *     int val;
   
7. *     TreeNode *left, *right;
   
8. *     TreeNode(int val) {
   
9. *         this->val = val;
   
10. *         this->left = this->right = NULL;
    
11. *     }
    
12. * }
    
13. */
    
14. class Solution {
    
15.     /**
    
16.      *@param inorder : A list of integers that inorder traversal of a tree
    
17.      *@param postorder : A list of integers that postorder traversal of a tree
    
18.      *@return : Root of a tree
    
19.      */
    
20. public:
    
21.     TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
    
22.         inPos.clear();
    
23.         int n = inorder.size();
    
24.         if (n == 0) {
    
25.             return NULL;
    
26.         }
    
27.         int i;
    
28.         for (i = 0; i < n; ++i) {
    
29.             inPos[inorder[i]] = i;
    
30.         }
    
31.         return construct(inorder, postorder, 0, n - 1, 0, n - 1);
    
32.     }
    
33. private:
    
34.     unordered_map<int, int> inPos;
    
35.    
    
36.     TreeNode *construct(vector<int> &in, vector<int> &post,
    
37.                         int ill, int irr, int pll, int prr) {
    
38.         int rootVal = post[prr];
    
39.         TreeNode *r = new TreeNode(rootVal);
    
40.         int i = inPos[rootVal];
    
41.         int len;
    
42.         if (i > ill) {
    
43.             len = i - ill;
    
44.             r->left = construct(in, post, ill, i - 1, pll, pll + len - 1);
    
45.         }
    
46.         if (i < irr) {
    
47.             len = irr - i;
    
48.             r->right = construct(in, post, i + 1, irr, prr - len, prr - 1);
    
49.         }
    
50.         return r;
    
51.     }
    
52. };

复制代码

复杂度2：时间O(N)，空间O(N)。

Construct Binary Tree from Preorder and Inorder Traversal
题意：给定前序和中序遍历，重建一棵二叉树。
解法1：递归解决，每次都要找出根节点位置。
代码1：

1. /**
   
2. * Definition of TreeNode:
   
3. * class TreeNode {
   
4. * public:
   
5. *     int val;
   
6. *     TreeNode *left, *right;
   
7. *     TreeNode(int val) {
   
8. *         this->val = val;
   
9. *         this->left = this->right = NULL;
   
10. *     }
    
11. * }
    
12. */
    
13. class Solution {
    
14.     /**
    
15.      *@param preorder : A list of integers that preorder traversal of a tree
    
16.      *@param inorder : A list of integers that inorder traversal of a tree
    
17.      *@return : Root of a tree
    
18.      */
    
19. public:
    
20.     TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
    
21.         int n = preorder.size();
    
22.         if (n == 0) {
    
23.             return NULL;
    
24.         }
    
25.         return construct(preorder, inorder, 0, n - 1, 0, n - 1);
    
26.     }
    
27. private:
    
28.     TreeNode *construct(vector<int> &pre, vector<int> &in,
    
29.                         int pll, int prr, int ill, int irr) {
    
30.         int rootVal = pre[pll];
    
31.         TreeNode *r = new TreeNode(rootVal);
    
32.         int i;
    
33.         for (i = ill; i <= irr; ++i) {
    
34.             if (in[i] == rootVal) {
    
35.                 break;
    
36.             }
    
37.         }
    
38.         int len;
    
39.         if (i > ill) {
    
40.             len = i - ill;
    
41.             r->left = construct(pre, in, pll + 1, pll + len, ill, i - 1);
    
42.         }
    
43.         if (i < irr) {
    
44.             len = irr - i;
    
45.             r->right = construct(pre, in, prr - len + 1, prr, i + 1, irr);
    
46.         }
    
47.         return r;
    
48.     }
    
49. };

复制代码

复杂度1：时间O(N * log(N))，最差可以到O(N ^ 2)，空间O(N)。

解法2：用hashing可以在O(1)时间找到根节点，所以总体时间可以达到O(N)。
代码2：

1. #include <unordered_map>
   
2. using namespace std;
   
3. /**
   
4. * Definition of TreeNode:
   
5. * class TreeNode {
   
6. * public:
   
7. *     int val;
   
8. *     TreeNode *left, *right;
   
9. *     TreeNode(int val) {
   
10. *         this->val = val;
    
11. *         this->left = this->right = NULL;
    
12. *     }
    
13. * }
    
14. */
    
15. class Solution {
    
16.     /**
    
17.      *@param preorder : A list of integers that preorder traversal of a tree
    
18.      *@param inorder : A list of integers that inorder traversal of a tree
    
19.      *@return : Root of a tree
    
20.      */
    
21. public:
    
22.     TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
    
23.         int n = preorder.size();
    
24.         if (n == 0) {
    
25.             return NULL;
    
26.         }
    
27.         int i;
    
28.         for (i = 0; i < n; ++i) {
    
29.             inPos[inorder[i]] = i;
    
30.         }
    
31.         return construct(preorder, inorder, 0, n - 1, 0, n - 1);
    
32.     }
    
33. private:
    
34.     unordered_map<int, int> inPos;
    
35.    
    
36.     TreeNode *construct(vector<int> &pre, vector<int> &in,
    
37.                         int pll, int prr, int ill, int irr) {
    
38.         int rootVal = pre[pll];
    
39.         TreeNode *r = new TreeNode(rootVal);
    
40.         int i = inPos[rootVal];
    
41.         int len;
    
42.         if (i > ill) {
    
43.             len = i - ill;
    
44.             r->left = construct(pre, in, pll + 1, pll + len, ill, i - 1);
    
45.         }
    
46.         if (i < irr) {
    
47.             len = irr - i;
    
48.             r->right = construct(pre, in, prr - len + 1, prr, i + 1, irr);
    
49.         }
    
50.         return r;
    
51.     }
    
52. };

复制代码

复杂度2：时间O(N)，空间O(N)。