PAT归纳总结——由二叉树的遍历结果构建二叉树

时间：2020-06-26 16:34:37 收藏：0 阅读：71

　　今天是6月26日到下个月的这个时候已经考过试了，为了让自己考一个更高的分数，所以我打算把PAT的相关题型做一个总结。目前想到的方法就是将相关的题型整理到一起然后，针对这种题型整理出一些方法。

　　有很多题目需要自己构造一棵二叉树有的是给出层序遍历的结果然后自己来构造二叉树，有的是给出二叉树的前序和中序或者给出二叉树的中序和后序来构造二叉树（如果给出前序和后序遍历的结果我们是不能够确定一棵二叉树的，很少数特殊的情况下可以唯一确定）

　　前一种情况可以通过队列来实现，具体的实现方法如下面的代码（没有整理，写的比较繁琐）：

 1 void buildTree() {
 2     root->value = que.front();
 3     que.pop();
 4     nodeQue.push(root);
 5     while(!que.empty()) {
 6         node parent = nodeQue.front();
 7         nodeQue.pop();
 8         node left = new Node();
 9         node right = new Node();
10         if (!que.empty()) {
11             left->value = que.front();
12             parent->left = left;
13             nodeQue.push(left);
14             que.pop();
15         }
16         if (!que.empty()) {
17             right->value = que.front();
18             parent->right = right;
19             nodeQue.push(right);
20             que.pop();
21         }
22     }
23 }

　　后一种树的构建方法是通过前序遍历和中序遍历以及后序遍历中结点的遍历次序来实现的。比如：前序遍历中第一个数字是根节点，然后找出根节点在中序遍历中的位置pos，pos左边的就是左子树，pos右边的就是右子树。然后再递归的查找左右子树，直到叶子节点为止。中序遍历和后序遍历的情况与之相同，只不过后序遍历的最后一个数字代表的是根节点。

　　具体的实现方法如下面的代码所示（这里给出了中序遍历和后序遍历来构建二叉树的例子）：

 1 // 由中序遍历和后序遍历构建二叉树
 2 node buildTree(int l1, int r1, int l2, int r2) {
 3     if (l1 > r1 || l2 > r2) return NULL;
 4     int val = postOrder[r1];
 5     node root = new Node(val);
 6     int pos = 0;
 7     for (int i = l2; i <= r2; ++i) {
 8         if (inOrder[i] == val) {
 9             pos = i;
10             break;
11         }
12     }
13     int rightLen = r2 - pos;
14     int leftLen = pos - l2;
15     root->right = buildTree(r1 - rightLen, r1 - 1, pos + 1, r2);
16     root->left = buildTree(l1, l1 + leftLen - 1, l2, l2 + leftLen - 1);
17     return root;
18 }

　　先写这么多，以后碰到其他的构建方法再补充。

原文：https://www.cnblogs.com/ruruozhenhao/p/13195354.html