LeetCode-Construct Binary Tree from Inorder and Postorder Traversal

数据结构的基础知识，根据中序、后序遍历或者先序、中序遍历构建二叉树；

典型的递归；

中序、后序的代码：

 1 /**
 2  * Definition for binary tree
 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     TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
13         // Start typing your C/C++ solution below
14         // DO NOT write int main() function
15         int m = inorder.size();
16         int n = postorder.size();
17         if (m != n || !m || !n) {
18             return NULL;
19         }
20         return build(inorder, 0, m - 1, postorder, 0, n - 1);
21     }
22     TreeNode *build(vector<int> &inorder, int m1, int m2, vector<int> &postorder, int n1, int n2) {
23         if (m1 > m2) {
24             return NULL;
25         }
26         TreeNode* node = new TreeNode(postorder[n2]);
27         int i;
28         for (i = m1; i <= m2; ++i) {
29             if (inorder[i] == postorder[n2]) {
30                 break;
31             }
32         }
33         node->left = build(inorder, m1, i - 1, postorder, n1, n1 + i - 1 - m1);
34         node->right = build(inorder, i + 1, m2, postorder, n2 - m2 + i, n2 - 1);
35         return node;
36     }
37 };

先序、中序的代码：

 1 /**
 2  * Definition for binary tree
 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     TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
13         // Start typing your C/C++ solution below
14         // DO NOT write int main() function
15         int m = preorder.size();
16         int n = inorder.size();
17         if (m != n || !m || !n) {
18             return NULL;
19         }
20         return build(preorder, 0, m - 1, inorder, 0, n - 1);
21     }
22     TreeNode *build(vector<int> &preorder, int m1, int m2, vector<int> &inorder, int n1, int n2) {
23         if (m1 > m2) {
24             return NULL;
25         }
26         int i;
27         for(i = n1; i <= n2; ++i) {
28             if (inorder[i] == preorder[m1]) {
29                 break;
30             }
31         }
32         TreeNode* node = new TreeNode(preorder[m1]);
33         node->left = build(preorder, m1 + 1, i - n1 + m1, inorder, n1, i - 1);
34         node->right = build(preorder, i - n1 + m1 + 1, m2, inorder, i + 1, n2);
35         return node;
36     }
37 };