文章目录
- 二叉树唯一确定
- 先序和中序递归构建二叉树的过程
- 先序和后序递归构建二叉树的过程
- 先序和后序递归构建二叉树的代码
- 如果二叉树不唯一，怎么处理
- 完整代码分析
- 自己的问题
二叉树唯一确定
对于一个二叉树，并不是说给出了先序和后序就是无法唯一确定的。只是说，在某些情况下，不能唯一确定。这里先给出结论，然后来分析。
当二叉树中某个节点仅仅只有一个孩子节点的时候，就无法更具其先序和后序唯一的确定一个二叉树。
例如：
preorder: 1 2 3 4
postorder:2 4 3 1
那么，构建出来的树可能是下面两种情况：
至于严格数学证明我这里无法给出。但是，如果你和我一样，都有点转牛角尖的话，可以自己多多去测试几个数据，然后时间一久，你就可以说服自己了。如果是这样的preorder和postorder的话，是可以唯一确定一个二叉树的。
preorder:1 2 3 4 6 7 5
postorder:2 6 7 4 5 3 1
确定的二叉树就是这样的：
很明显，因为这个二叉树所有的节点仅仅只有二个或者没有（叶子节点）。所以，这个二叉树是可以唯一确定的。
先序和中序递归构建二叉树的过程
大家下来看一下维基百科上对于二叉树定义：
In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A recursive definition using just set theory notions is that a (non-empty) binary tree is a tuple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set.Some authors allow the binary tree to be the empty set as well.
也就是说：二叉树的定义是一个递归（recursive）的。我相信大家在学习二叉树的构建的时候老师也讲过递归构建二叉树。在树的数据结构中，递归还是很有必要掌握的，毕竟有很多算法都和这个有关。
那么，接下来，我们就采用递归的构造方法来创建这个二叉树。为了说明清楚这个构建的过程，有必要提一下先序或者后序和中序是怎么构建一个二叉树的。下面以先序和中序举例：
preorder:1 2 3 4 6 7 5
inorder:2 1 6 4 7 3 5
构建的方法如下：
在preorder序列中，找到第一个节点，根据先序遍历的规则（根 左 右），所以节点1是根节点。然后我们利用中序遍历的规则（左 根 右），只要我们在inorder序列中找到1节点，那么在它的左边和右边的就分别是1节点的左孩子和右孩子了。结合代码看一下：
//preorder的下标为[preLmpreR]
//inorder的下标为[inL,inR]
Node* create(int preL, int preR, int inL, int inR)
{//伏笔（1）if (preL > preR){return NULL;}Node *root = new Node;root->data = preorder[preL];//（伏笔2）//root->left = root->right = NULL;//（伏笔3）/*if (preL == preR){return root;}*/int tmp = root->data;int k = inL;for (; k <= inR; k++){if (inorder[k] == tmp){break;}}int num = k- inL;root->left = create(preL + 1, preL + num, inL, k- 1);root->right = create(preL + num + 1, preR, k+ 1, inR);return root;
}
有些对递归不太懂的同学，可能看到这里就懵了。那么我来说一个我方便理解的方法。就是你不要想太多：例如1节点左右孩子，3节点还有左右孩子啊。递归如果你想的太深入，就很容易把自己想晕。所以，你应该仅仅只想简单情况，具体复杂的情况要计算机自己去执行。那么这里，你就先仅仅只想1节点就只有两个孩子，那么做下面这两个语句就可以了：
root->left = create(preL + 1, preL + num, inL, i - 1);
root->right = create(preL + num + 1, preR, i + 1, inR);
这里就是在说：构建1节点的左孩子然后赋值給left；然后构建1节点的右孩子赋值給right。你先当作preL+1和pre+num相等，inL和i-1相等，那么是不是就仅仅只包含一个节点，就不会继续递归了，然后你自己就可以模拟出来构建的情况了。这里大家就自行体会，我一开始也是有点难理解，但是你多想几天，时间会帮你克服的。下面的中可能会出现（伏笔x）之类的字，大家先忽略，最后会有用的。上面的代码中也有伏笔，注意看。最后要和先序和后序建立二叉树的代码做比较的。
上面一个很重要的操作就是找到preorder中1节点（根节点）（伏笔4）在inorder序列中的位置。因为根据中序遍历的规则，这个节点1的左边和右边就是1节点的左子树和右子树在inorde序列中的数据。先序和中序之所以可以唯一确定一个二叉树，就是因为可以根据inorder来确定每一个根节点的左右子树。同理，中序和后序也是一样的。
先序和后序递归构建二叉树的过程
但是，根据先序和后序的遍历规则，根节点不会在左子树和右子树的中间了。但是大家看上面的先序遍历：
preorder:1 2 3 4 6 7 5
对于序列1 2 3 来说，1是根节点，2是左孩子，3是右孩子。（当然，2和3不一定就是1的左孩子和右孩子）。但是对于序列2 3 4 来说，2是根节点，3是左孩子，4是右孩子（当然，3和4不一定就是2的左孩子和右孩子）。但是，可以确定的就是2一定可以当作根节点来对待。重点来了：我在preorde序列中找到根节点1，然后找到下一个节点2，将其当作根节点，然后在postorder中去找到这个节点2。根据后序遍历的规则（左右根），那么2节点的前面的就是2节点自己的左孩子和右孩子，2节点和1节点之间的就是1号节点的孩子。当然，2肯定也是1号节点的孩子节点（可能是左孩子，也可能是右孩子）。那么，如果2节点和1节点之间没有节点了，那么是不是说明1节点仅仅只有2节点这样一个孩子。再根据上面的结论：
当二叉树中某个节点仅仅只有一个孩子节点的时候，就无法更具其先序和后序唯一的确定一个二叉树。
此时应该无法确定一个唯一的二叉树。上面的重点位置（如果看不懂的话）一定要反复体会。因为这个涉及到代码的实现了。
先序和后序递归构建二叉树的代码
Node *create(int preL, int preR, int posL, int posR)
{//伏笔（1）//这个可以作为递归结束条件if(preL > preR){return NULL;}Node *root = (Node*)malloc(sizeof(Node));root->data = preorder[preL];//伏笔（2）root->left = NULL;root->right = NULL;//伏笔（3）//这个可以作为递归结束条件if (preL == preR)return root;//以先序遍历的根节点后一个结点为根节点去查看左右子树int tmp = preorder[preL + 1];int k = posL;//在后序遍历中查看for (; k <= posR - 1; k++){if (postorder[k] == tmp){break;}}int num = k - posL;if (k != posR - 1){root->left = create(preL + 1, preL + 1 + num, posL, k);root->right = create(preL + num + 2, preR, k + 1, posR - 1);}else{flag = false;//伏笔（5）root->left = create(preL + 1, preL + 1 + num, posL, k);}return root;
}
上面的伏笔都是我写代码过程中遇到的问题。现在来一一解释。
伏笔（1）（2）（3），可以一次性讲完。（1）（3）都是递归函数的退出条件。至于为什么这两个都可以作为递归的条件，大家可以自己简单模拟一下，或者自己上机调试。对于先序或者后序和中序来确定一个二叉树使用（1）是可以的，但是对于先序和后序的，就只能使用（2）（3）的组合。至于原因就是：在调试过程中我发现：最后会导致preorder下标越界。究其原因就是因为在递归的退出条件是：if(preL>preR)才会退出。但是，其实preL==preR就可以退出了，因为此时就是已经可以唯一确定一个节点了，if(preL>preR)就是会多执行一次，然后返回NULL。所以(2)(3)要一起使用，在返回之前要給root->left=root->right=NULL初始化。但是使用if(preL>preR)就不用担心，因为此时会return NULL，不需要自己手动初始化。这里是需要对这部分递归熟悉一点才可以理解我说的意思（估计我也没有表达清楚我的意思），所以大家多多看几遍，然后测试几遍就好理解一点。
大家仔细去看，先序和中序求树的代码中，num和k的意思和先序和后序求树中有点发生变化了。在先序和中序求树中,num是代表根节点左孩子的个数，k代表根节点的位置，所以k是没有出现在create()形参，因为这就是要求inorder[k]节点的左右孩子，所以自然就不包括自己了。先序和后序求树中num代表的就是preorder[preL+1]这个节点的左右孩子的个数，但是因为preL+1是preL的孩子节点，而且一定是左孩子节点。至于为什么一定是左孩子节点，我先留在这里，后面会说明。同时，这个事情还与上面代码中伏笔（5）有关。回到正题，既然preL+1一定是preL的左孩子，num+1的个数就是preL节点的左孩子的个数。所以，就会有下面这个代码：
root->left = create(preL + 1, preL + 1 + num, posL, k);
preL+1是preL左孩子的第一个下标（也相当于是preL所有左孩子中的根节点）。preL+num+1就是preL节点左孩子的在先序序列中最后一个下标。因为postorder[k]=preorder[preL]，所以在后序序列中最后一个下标就是k。因为postorder[k]是从posL开始找起的，说明在[posL,k]这个序列中，所有的都是preL的左孩子。那么preL的右孩子也是一样的，我就不多说了。大家如果没有理解的话，可以自己测试上面我给出的数据，加上调试代码，多多看几遍就可以懂了。
root->right = create(preL + num + 2, preR, k + 1, posR - 1);
如果二叉树不唯一，怎么处理
在讲伏笔（5）之前，先讲点别的。我之所以写这个文章就是因为我在做PAT 甲级1119号题目的时候，发现自己写不出来。然后就去看大家的博客，发现都不怎么清楚。基本上就是只有代码，解释的都不多。而且清一色的在处理不唯一的情况的时候，都是将其root->right赋值。也就是说，都是默认为右孩子。（如果你听不懂我在说什么，建议先看看这个题目）我是一个喜欢转牛角尖的人，而且我觉得这个知识也应该掌握，毕竟就是一个递归的使用。大家可以看到上面的代码，我采用的方式是当二叉树不唯一的时候，形成左子树。那么大家可能会想，是不是左子树和右子树都可以了，其实这个就得看你采用什么方法了。以下内容都是我自己测试出来，不一定具有普遍性（但是至少我采用的两种不同的方法在PAT上都测试通过了，说明我的结论应该没有问题）。
前面提到，我们采用的就是找preL后面的一个节点preL+1，去当做根节点，然后去到postorder序列里面去找到这个根节点，然后做一些操作。而且我认为preL+1一定就是preL的左孩子。这个要反推才好理解。因为我最后要构建一个二叉树出来，所有这个二叉树是是固定的。所有对于一个二叉树固定的来说，在先序遍历中，根节点后面一定是它的左孩子。因为这个二叉树是唯一的，所以每一个节点都应该有两个节点或者为叶子节点，如果仅仅只有一个节点，那么也一定是左子树。因为我们的代码就是这么写的，就是认为preL+1一定就是preL的左孩子。那么你可以会问，这样子不会有问题吗？你要这样想，如果这个二叉树是可以唯一确定的，那么preL+1一定是preL的左孩子（因为二叉树可以唯一确定，所以必定就是两个节点或者为叶子节点）。如果不可以唯一确定（不能唯一确定固定原因就是在在于这个节点既可以为左孩子，又可以为右孩子），那么我就在构建这个二叉树的时候，默认为左孩子就可以了，所以我就能建立出二叉树。（看不懂很正常，因为都是我自己的话，一点都不官方与严谨。但是我觉得可以給读者一个思考的方向。欢迎下面评论交流）
如果你还有疑问，你可以把上面的代码伏笔（5）改成下面这个代码：
root->right = create(preL + num + 2, preR, k + 1, posR - 1);
也就是你在二叉树不唯一的时候，默认为右孩子。然后测试数据：
4
1 2 3 4
2 4 3 1
就会报错。说明，你在采用以先序遍历中preL+1为分割节点到postorde序列中找的时候，在二叉树不能确定的时候，只能默认为左孩子。 但是网络上很多都是默认右孩子，那么他们是怎么思考的呢？下面先给出代码：然后分析
Node *create(int preL, int preR, int posL, int posR)
{Node *root = (Node*)malloc(sizeof(Node));root->data = preorder[preL];root->left = NULL;root->right = NULL;//这个代码一定的要，不然就会报错if (preL == preR)return root;//以后序遍历的根节点前一个节点为分割节点int tmp = postorder[posR - 1];int k = preL+1;for ( ;k<=preR;k++){if (preorder[k] == tmp){break;}}int num = k - (preL+1);if (k!=preL+1){root->left = create(preL + 1, k-1, posL, posL+num-1);root->right = create(k, preR, posL +num, posR-1);}else{flag = false;root->right = create(k, preR, posL + num, posR - 1);}return root;
}
同样的套路分析，根据后序遍历的规则（左 右 根）把posR-1当作posR的右孩子。那么，在先序序列中，找到了，下标为k。因为preorder[preL]==postorder[posR],所以posR-1也是preL也是的右孩子。根据先序遍历的规则（根 左 右），从preL+1开始，到k就是preL的所有直接孩子节点。所以，[preL+1,k]都是preL的孩子。然后num什么的就都可以分析出来了。所以，在这里，就是二叉树不唯一的时候默认为右孩子节点才对。
完整代码分析
下面将会给出两中代码，则可以直接通过PAT 1119这到题。大家可以针对上面说的两种情况，自己去试试。如果我就不那么做，会出现什么样的问题。这样子可能有利于大家理解。
//以后序遍历的根节点前一个节点为分割节点
#include<iostream>
#include<vector>using namespace std;
typedef struct Node
{int data;struct Node *left;struct Node *right;
}Node;vector<int> preorder;
vector<int> postorder;
bool flag = true;
vector<int> ans;Node *create(int preL, int preR, int posL, int posR)
{Node *root = (Node*)malloc(sizeof(Node));root->data = preorder[preL];root->left = NULL;root->right = NULL;if (preL == preR)return root;//以后序遍历的根节点前一个节点为分割节点int tmp = postorder[posR - 1];int k = preL+1;for ( ;k<=preR;k++){if (preorder[k] == tmp){break;}}int num = k - (preL+1);if (k!=preL+1){root->left = create(preL + 1, k-1, posL, posL+num-1);root->right = create(k, preR, posL +num, posR-1);}else{flag = false;root->right = create(k, preR, posL + num, posR - 1);}return root;
}void inorder(Node *root)
{if (!root){return;}inorder(root->left);ans.push_back(root->data);inorder(root->right);
}int main()
{int N;cin >> N;int tmp;for (int i = 0; i < N; i++){cin >> tmp;preorder.push_back(tmp);}for (int i = 0; i < N; i++){cin >> tmp;postorder.push_back(tmp);}Node *root = create(0, preorder.size() - 1, 0, postorder.size() - 1);if (flag){cout << "Yes" << endl;}else{cout << "No" << endl;}inorder(root);for (int i = 0; i < ans.size(); i++){cout << ans[i];if (i != ans.size() - 1){cout << " ";}}return 0;
}
//以先序遍历的根节点后一个结点为分割节点
#include<iostream>
#include<vector>using namespace std;
typedef struct Node
{int data;struct Node *left;struct Node *right;
}Node;vector<int> preorder;
vector<int> postorder;
bool flag = true;
vector<int> ans;Node *create(int preL, int preR, int posL, int posR)
{Node *root = (Node*)malloc(sizeof(Node));root->data = preorder[preL];root->left = NULL;root->right = NULL;if (preL == preR)return root;//以先序遍历的根节点后一个结点为分割节点int tmp = preorder[preL + 1];int k = posL;for (; k <= posR - 1; k++){if (postorder[k] == tmp){break;}}int num = k - posL;if (k != posR - 1){root->left = create(preL + 1, preL + 1 + num, posL, k);root->right = create(preL + num + 2, preR, k + 1, posR - 1);}else{flag = false;root->left = create(preL + 1, preL + 1 + num, posL, k);}return root;
}void inorder(Node *root)
{if (!root){return;}inorder(root->left);ans.push_back(root->data);inorder(root->right);
}int main()
{int N;cin >> N;int tmp;for (int i = 0; i < N; i++){cin >> tmp;preorder.push_back(tmp);}for (int i = 0; i < N; i++){cin >> tmp;postorder.push_back(tmp);}Node *root = create(0, preorder.size() - 1, 0, postorder.size() - 1);if (flag){cout << "Yes" << endl;}else{cout << "No" << endl;}inorder(root);for (int i = 0; i < ans.size(); i++){cout << ans[i];if (i != ans.size() - 1){cout << " ";}}return 0;
}
自己的问题
10月15日更新
我发现我上面有点问题，下面是我总结的：
对于递归出口条件：
在先序和中序推出这棵树：1.if (preL > preR) {}适合于只有一个孩子节点或者叶子节点；仅仅使用这个判断不会报错2.if (preL == preR){}仅仅适合于叶子节点的构造，如果对于只有一个孩子节点的来说，就会出现下标越界；仅仅使用这个判断就会报错
在中序和后序推出这棵树：1.if (preL > preR){}适合于只有一个孩子节点或者叶子节点；仅仅使用这个判断不会报错2.if (preL == preR){}仅仅适合于叶子节点的构造，如果对于只有一个孩子节点的来说，就会出现下标越界；仅仅使用这个判断就会报错
在先序和后序推出这颗树：1.if (preL > preR){}仅仅使用这个判断就会报错这个会报错的原因在于：下标越界。为什么会出现这样的情况，我觉得就是因为我们采用的思想就是（假设这里是以prel+1作为分割点去后序遍历中找）：认为preL+1就是preL的左孩子，但是，在仅仅通过先序来判断的话，preL+1可能于preL没有任何关系。也就是说，preL+1可能就是另外一颗子树上面的节点。但是程序无法知道，而且你仅仅使用了一个 if (preL > preR){};如果没有到叶子节点话形参还是在变大，最后导致下标越界。2.if (preL == preR){}仅仅使用这个判断不会报错。之前上面的说到这里，针对于仅仅只有一个孩子节点的时候这种判断在这里是会下标越界的。那么为什么在这里不仅没有越界，反而还可以成功呢？原因在于当先序和后序无法推导出一颗唯一的二叉树的时候，我的算法就会默认其是根节点的左子树（当然，你如果想要默认为右子树也是可以，不过就要稍微修改一下代码），那么也就是说，此时仅仅只会給root->left赋值，而不会给root->right赋值。而你现在回头过去看一下，是不是在先序和中序推出这棵树（中序和后序推出这棵树）仅仅使用 if (preL == preR){} 的时候，如果root仅仅只有左孩子的话，那么你在递归调用root->left赋值结束之后，再给root->right赋值的时候，如果不使用if (preL > preR){}就会出现下标越界。但是，在先序和后序推出这颗树的时候就不会了，因为如果可以唯一的确定一棵树，那么节点必然都是有两个孩子或者是叶子节点。如果只有一个节点，那么就无法唯一的推出这棵树，所以代码中就仅仅只会对默认左（或者右）孩子进行赋值，从而即时没有写 if(preL>preR){}也不会导致下标越界。综上所述：如果想要简单点写代码，然后又可以使用于所有的情况，那么就是这两个判断条件都写上去就欧克了。这个就是万能操作。
