今天看到关于几道关于给你一个中序遍历 再给你一个前序或者后序遍历, 让你还原二叉树的类型题目, 下面来就方法来说简单做一下分享. 当然, 可能有不太对的地方, 存在错误还请指正~
首先, 我们得明确一个问题, 就是一个二叉树只给你其中一种遍历方式能够还原出这棵树吗?
直接说结论, 不能!
我们举个例子, 就拿前序遍历来说, 假如说给你的前序遍历是"ABCDEF", 请你还原这棵树. 我们都知道, 前序遍历是根->左子树->右子树的这样一个逻辑. 我们尝试还原一下这棵树:
实际上第一个结点我们确定他就是根, 但是第二个结点放到哪? A的左子树的根还是右子树的根? 我们就不确定了.
因此, 假设二叉树只给你一种遍历方式的话是不能还原出原来的树的.
为什么不能还原? 就是不确定是二叉树的左子树或者右子树的根嘛… 就是这么简单~
但是, 如果告诉你这是一颗完全二叉树, 然后再告诉你前序遍历是"ABCDEF"呢? 这种情况是否可以还原呢?
可以 因为告诉你遍历方式并且告诉你这是完全二叉树, 变相告诉你这颗树的大致结构是什么样子了.
不妨我们再来看个例子: 假设该树是一颗完全二叉树, 并且该树的前序遍历是"ABCDEF", 请你还原这颗完全二叉树:
那我们分享一下下面这几道题:
1.某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为（ ）
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA
2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为（）
A E
B F
C G
D H
3.设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为____。
A adbce
B decab
C debac
D abcde
4.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列
为
A FEDCBA
B CBAFED
C DEFCBA
D ABCDEF
这种题目如何做呢?
总体思路: 这类题任意给你一个前序/后序遍历, 再给你中序遍历进行还原树的话. 就是用前序/后序遍历去找根, 然后在中序遍历的基础上划分. 因为中序遍历是左 根 右 的形式给出的, 不好找根, 但是前序或者后序遍历根要么在最开始要么在最后面, 因此前/后序遍历比较适合找根.
当我们被给予两种遍历方式并需要还原树的结构时，通常会利用以下特性：
- 前序遍历（Preorder Traversal）：根节点 -> 左子树 -> 右子树。由于根节点总是第一个被访问，所以前序遍历非常适合用来确定当前子树的根节点。
- 中序遍历（Inorder Traversal）：左子树 -> 根节点 -> 右子树。中序遍历的特性是根节点将遍历序列分为左右两个子树，这使得中序遍历非常适合用来划分左右子树。
- 后序遍历（Postorder Traversal）：左子树 -> 右子树 -> 根节点。虽然根节点是最后一个被访问的，但在没有前序或中序遍历的情况下，单独使用后序遍历来还原树结构会比较困难，因为无法直接确定根节点的位置（除非结合其他信息，如节点数量或树的形状等）。
在实际应用中，当我们被给予前序（或后序）遍历和中序遍历时，通常的解题步骤如下：
- 使用前序（或后序）遍历的第一个（或最后一个）节点作为当前子树的根节点。
- 在中序遍历中找到该根节点的位置，从而划分出左右子树的中序遍历序列。
- 根据划分后的中序遍历序列，在前序（或后序）遍历中找到对应的左右子树部分。
- 递归地对左右子树进行上述步骤，直到所有节点都被处理完毕。
题解:
EOF
