重建二叉树

二叉树重建，必须要有中序遍历结果，再加上前序或后序的遍历结果。

前序遍历的第一个数，就是根节点，根据这个数在中序遍历的位置，左边部分为左子树，右边部分为右子树。

后序遍历的最后一个数，就是根节点，根据这个数在中序遍历的位置，左边部分为左子树，右边部分为右子树。

1、前序+中序（105. Construct Binary Tree from Preorder and Inorder Traversal）

 1 class Solution {
 2 public:
 3     TreeNode* helper(vector<int>& preorder, vector<int>& inorder, int p1, int p2, int i1, int i2) {
 4         if (p1 > p2)
 5             return nullptr;
 6         int num = preorder[p1];
 7         int len;
 8         for (len = 0; len <= i2-i1; ++len) {
 9             if (inorder[len+i1] == num)
10                 break;
11         }
12         TreeNode *tree = new TreeNode(num);
13         tree->left = helper(preorder, inorder, p1+1, p1+len, i1, i1+len-1);
14         tree->right = helper(preorder, inorder, p1+len+1, p2, i1+len+1, i2);
15         return tree;
16     }
17     TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
18         int len = preorder.size();
19         return helper(preorder, inorder, 0, len-1, 0, len-1);
20     }
21 };

2、后序+中序（106. Construct Binary Tree from Inorder and Postorder Traversal）

 1 class Solution {
 2 public:
 3     TreeNode* helper(vector<int>& inorder, vector<int>& postorder, int p1, int p2, int i1, int i2) {
 4         if (p1 > p2)
 5             return nullptr;
 6         int num = postorder[p2];
 7         int len;
 8         for (len = 0; len <= i2-i1; ++len) {
 9             if (inorder[len+i1] == num)
10                 break;
11         }
12         TreeNode *tree = new TreeNode(num);
13         tree->left = helper(inorder, postorder, p1, p1+len-1, i1, i1+len-1);
14         tree->right = helper(inorder, postorder, p1+len, p2-1, i1+len+1, i2);
15         return tree;
16     }
17     TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
18         int len = inorder.size();
19         return helper(inorder, postorder, 0, len-1, 0, len-1);
20     }
21 };

重建二叉树

推荐阅读