先序序列和中序序列构造二叉树
验证代码请到：https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
二叉树的结点结构
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
先序遍历有个特点就是在根结点与两个子结点三个结点中总是先遍历根结点，因此先序遍历序列中的第一个元素一定是根结点，而中序遍历则是先遍历完左子树所有结点后再遍历根结点，那么我们就可以利用这两个序列的各自的性质，在中序序列中找到当前的根结点，设其位置为i，那么很明显，中序序列中在位置i左边的都是当前结点的左子树结点，在其右边的都是右子树的结点。由于先序遍历是先遍历一个根结点，接着遍历所有左子树，再遍历所有右子树，因此先序遍历的位置i一定是左子树的最后一个结点位置，其后面是右子树的结点。
例如下面的例子，从中序遍历序列中可以很容易看出，结点1、3是根结点的左子树，结点4、2、5是右子树。
root
/ \
1 2
/ / \
3 4 5
preorder: root 1 3 2 4 5
inorder: 3 1 root 4 2 5
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
return dfs(preorder, 0, n-1, inorder, 0, n-1);
}
TreeNode* dfs(vector<int>& pre, int ps, int pe, vector<int>& in, int is, int ie) {
if (ps > pe || is > ie) return NULL;//序列用完了
TreeNode *root = new TreeNode(pre[ps]);
int i;
for (i = is; i <= ie; i++) {//在中序序列中找root结点
if (in[i] == pre[ps]) {
break;
}
}
root->left = dfs(pre, ps+1, ps+i-is, in, is, ie-1);
root->right = dfs(pre, ps+i-is+1, pe, in, i+1, ie);
return root;
}
/*is means the start index of inorder
*ie means the last index of inorder
*ps means the start index of preorder
*pe means the last index of preorder
*/
后序序列和中序序列构造二叉树
代码验证请到：https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
二叉树结点结构
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
后序遍历与先序遍历只有一个不同的地方，那就是先序遍历是先遍历根结点，再遍历左右子树；而后序遍历则是先遍历左右子树，再遍历根结点。因此先序遍历序列的第一个元素就是当前的根结点，而后序遍历的倒数第一个元素就是当前的根结点。
因此后序遍历与中序遍历序列构造二叉树就与先序遍历序列和中序遍历序列遍历二叉树贼像！只需要主意一点：先序遍历的第一个结点为根结点，而后序遍历的最后一个结点为根结点。
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int n = inorder.size();
return dfs(inorder, 0, n-1, postorder, 0, n-1);
}
TreeNode* dfs(vector<int>& in, int is, int ie, vector<int>& po, int ps, int pe) {
if (is > ie || ps > pe) return NULL;
TreeNode *root = new TreeNode(po[pe]);
int i;
for (i = is; i <= ie; i++) {
if (in[i] == po[pe]) {
break;
}
}
root->left = dfs(in, is, i-1, po, ps, ps+i-is-1);
root->right = dfs(in, i+1, ie, po, ps+i-is, pe-1);
return root;
}
/*is means the start index of inorder
*ie means the last index of inorder
*ps means the start index of postorder
*pe means the last index of postorder
*/
先序序列和后序序列构造二叉树
代码验证请到：https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
二叉树结点结构
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
通过先序序列和后序序列构造二叉树有三个需要注意的地方：
- 二叉树中不能存在相同结点
- 有很多结构不同的二叉树，它们的之间的先序（后序）序列是一样的
- 除叶结点以外，其它所有结点都需要有左右孩子，否则不可能重构二叉树
二叉树中不能有相同结点？
二叉树中如果存在相同的结点，那么就不能有效确定左右子树各自的先序序列和后序序列。例如：
二叉树：
1
/ \
2 2
/ \
3 2
先序序列：1 2 3 2 2
后序序列：3 2 2 2 1
我们很容易通过先序序列的第一个元素或者后序序列的最后一个元素确定当前的根结点为1，
我们也可以通过先序序列第二个元素确定左子树的根结点为2，那我们就去后序序列中找2，
但是我们无法确定是哪一个2，因此就不能有效划分左右子树各自的先序序列和后序序列了。
结构不同的二叉树有相同的先序（后序）序列？
确实存在一些二叉树，它们结构不同，但是先序序列和后序序列都相同，例如
二叉树1： 二叉树2：
1 1
/ \ / \
2 2 2 2
/ \ / \
3 2 3 2
先序序列：1 2 3 2 2 先序序列：1 2 3 2 2
后序序列：3 2 2 2 1 后序序列：3 2 2 2 1
或者
二叉树3： 二叉树4：
1 1
/ \
2 2
先序序列：1 2 先序序列：1 2
后序序列：2 1 后序序列：2 1
给你一组先序序列和后序序列，你打算构造哪棵二叉树呢？
除叶结点外的结点都要有左右结点？
确实，因为只有存在左右子树，才能有效划分左右子树各自的先序序列和后序序列啊！例如：
二叉树1： 二叉树2：
1 1
/ \
2 2
先序序列：1 2 先序序列：1 2
后序序列：2 1 后序序列：2 1
如果非叶子结点只有左右子结点中的一个，
那么就无法从先序序列和后序序列中划分其左右子树各自的序列。
因为我们不知道该根结点下面是有一个子结点还是左右两个子结点，
这种不确定性让我们无法划分左右子树的序列。
在上述条件的限制下，我们就可以说：
A preorder traversal is:
(root node) (preorder of left branch) (preorder of right branch)While a postorder traversal is:
(postorder of left branch) (postorder of right branch) (root node)
TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
int n = pre.size();
return dfs(pre, 0, n-1, post, 0, n-1);
}
TreeNode* dfs(vector<int>& pre, int pre_s, int pre_e, vector<int>& post, int post_s, int post_e) {
if (pre_s > pre_e || post_s > post_e) return NULL;
TreeNode* root = new TreeNode(pre[pre_s]);
if (post_s == post_e) {
return root;
}
int i;
for (i = post_s; i <= post_e; i++) {
if (post[i] == pre[pre_s+1]) {
break;
}
}
root->left = dfs(pre, pre_s+1, pre_s+1+i-post_s, post, post_s, i);
root->right = dfs(pre, pre_s+2+i-post_s, pre_e, post, i+1, post_e-1);
return root;
}
/*pre_s means the start index of preorder
*pre_e means the last index of preorder
*post_s means the start index of postorder
*post_e means the last index of postorder
*/
收藏版：递归+迭代
来源：https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/discuss/161268/C%2B%2BJavaPython-One-Pass-Real-O(N)
递归
int preIndex = 0, posIndex = 0;
TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
TreeNode* root = new TreeNode(pre[preIndex++]);
if (root->val != post[posIndex])
root->left = constructFromPrePost(pre, post);
if (root->val != post[posIndex])
root->right = constructFromPrePost(pre, post);
posIndex++;
return root;
}
迭代
TreeNode* constructFromPrePost(vector<int> pre, vector<int> post) {
vector<TreeNode*> s;
s.push_back(new TreeNode(pre[0]));
for (int i = 1, j = 0; i < pre.size(); ++i) {
TreeNode* node = new TreeNode(pre[i]);
while (s.back()->val == post[j])
s.pop_back(), j++;
if (s.back()->left == NULL) s.back()->left = node;
else s.back()->right = node;
s.push_back(node);
}
return s[0];
}
通过先序序列和中序序列生成后序序列
已知一棵二叉树所有的节点值都不同，给定这棵树正确的先序和中序数组，不要重建整棵树，而是通过这两个数组直接生成正确的后序数组。
引用《程序员代码面试指南》中的例子
举例说明生成后序数组的过程，假设pre=[1，2，4，5，3，6，7]，in=[4，2，5，1， 6，3，7]。
- 根据pre和in的长度，生成长度为7的后序数组pos，按以下规则从右到左填满pos。
- 根据[1，2，4，5，3，6，7]和[4，2，5，1，6，3，7]，设置pos[6]=1，即先序数组最左边的值。根据1把in划分成[4，2，5]和[6，3，7]，pre中1的右边部分根据这两部分等长划分出[2，4，5]和[3，6，7]。[2，4，5]和[4，2，5]一组，[3，6，7]和[6，3，7]一 组。
- 根据[3，6，7]和[6，3，7]，设置pos[5]=3，再次划分出[6]（来自[3，6，7]）和 [6]（来自[6，3，7]）一组，[7]（来自[3，6，7]）和[7]（来自[6，3，7]）一组。
- 根据[7]和[7]设置pos[4]=7。
- 根据[6]和[6]设置pos[3]=6。
- 根据[2，4，5]和[4，2，5]，设置pos[2]=2，再次划分出[4]（来自[2，4，5]）和 [4]（来自[4，2，5]）一组，[5]（来自[[2，4，5]）和[5]（来自[4，2，5]）一组。
- 根据[5]和[5]设置pos[1]=5。
- 根据[4]和[4]设置pos[0]=4
如上过程简单总结为：根据当前的先序和中序数组，设置后序数组最右边的值，然后划分出左子树的先序、中序数组，以及右子树的先序、中序数组，先根据右子树的划分设置好后序数组，再根据左子树的划分，从右边到左边依次设置好后序数组的全部位置。
//该代码正确性未经验证，改自《程序员代码面试指南》
vector<int> getPos(vector<int> &pre, vector<int> &in) {
int n = pre.size();
vector<int> pos(n);
setPos(pre, 0, n-1, in, 0, n-1, pos, n-1);
return pos;
}
// 从右往左依次填好后序数组s
// si为后序数组s该填的位置
// 返回值为下一个s该填的位置
int setPos(vector<int> &p, int pi, int pj,
vector<int> &n, int ni, int nj,
vector<int> &s, int si) {
if (pi > pj) return si;
s[si--] = p[pi];
int i;
for (i = 0; i < p.size(); i++) {
if (p[pi] == n[i]) {
break;
}
}
si = setPos(p, pj-nj+i+1, pj, n, i+1, nj, s, si);
return setPost(p, pi+1, pi+i-ni, n, ni, i-1, s, si);
}