先序中序后序两两结合重建二叉树

我不是女神ヾ 2022-04-15 04:22 214阅读 0赞

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，[树的遍历][Link 1]实质上是将二叉树的各个结点转换成为一个线性序列来表示。

设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。

### 先序遍历 ###

首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树，C语言代码如下：

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 </td> 
 <td> <code>void</code>&nbsp;<code>XXBL(tree&nbsp;*root){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//DoSomethingwithroot</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(root-&gt;lchild!=NULL)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>XXBL(root-&gt;lchild);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(root-&gt;rchild!=NULL)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>XXBL(root-&gt;rchild);</code> <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

### 中序遍历 ###

首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树，C语言代码如下

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 </td> 
 <td> <code>void</code>&nbsp;<code>ZXBL(tree&nbsp;*root)</code> <code>{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(root-&gt;lchild!=NULL)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>ZXBL(root-&gt;lchild);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//Do&nbsp;something&nbsp;with&nbsp;root</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(root-&gt;rchild!=NULL)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>ZXBL(root-&gt;rchild);</code> <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

### 后序遍历 ###

首先后序遍历左（右）子树，再后序遍历右（左）子树，最后访问根，C语言代码如下

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 </td> 
 <td> <code>void</code>&nbsp;<code>HXBL(tree&nbsp;*root){ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(root-&gt;lchild!=NULL)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>HXBL(root-&gt;lchild);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(root-&gt;rchild!=NULL)</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>HXBL(root-&gt;rchild);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//Do&nbsp;something&nbsp;with&nbsp;root</code> <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>

### 层次遍历 ###

即按照层次访问，通常用[队列][Link 2]来做。访问根，访问子女，再访问子女的子女（越往后的层次越低）（两个子女的级别相同）

# 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。 #

我们首先找到根结点：一定是先序遍历序列的第一个元素：1

![20181121154249618.png][]

然后，在中序序列寻找根，把中序序列分为两个序列左子树4，7，2和右子树5，3，8，6

把先序序列也分为两个： 左子树2，4，7和右子树3，5，6，8

对左右重复同样的过程：

先看左子树：先序序列4，7，2，说明4一定是左子树的根

![201811211543214.png][]

把2，4，7分为2和7两个序列，再重复过程，左边确定完毕。

![20181121154345209.png][]

右子树同样：中序序列为5，3，8，6，先序序列为：3，5，6，8

取先序头，3.一定是根

![20181121154451150.png][]

把中序序列分为 5和8，6两个序列

对应的先序序列为 5和6，8两个序列

然后确定了5是3的左孩子

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70][]

对于先序序列6，8和中序序列8，6

还是先取先序的头，6

![20181121154713894.png][]

现在只有8，中序序列8在左边，是左孩子。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1][]

结束。

我们总结一下这种方法的过程：

1、根据先序序列确定当前树的根（第一个元素）。

2、在中序序列中找到根，并以根为分界分为两个序列。

3、这样，确定了左子树元素个数，把先序序列也分为两个。

对左右子树（对应的序列）重复相同的过程。

我们把思路用代码实现：

# -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        # 返回构造的TreeNode根节点
        def reConstructBinaryTree(self, pre, tin):
            # write code here/
            #pre-先序数组   tin->中序数组
            if len(pre) == 0:
                return None
            root = TreeNode(pre[0])//第一个元素为根
            pos = tin.index(pre[0])//划分左右子树
            root.left = self.reConstructBinaryTree( pre[1:1+pos], tin[:pos])
            root.right = self.reConstructBinaryTree( pre[pos+1:], tin[pos+1:])
            return root

# 输入某二叉树的后序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字 #

思路是类似的，只是我们确定根的时候，取后序序列的最后一个元素即可。

# 输入某二叉树的后序遍历和先序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字 #

我们直白的表述一下，前序是中左右，后序是左右中。

所以，我们凭先序和后序序列其实是无法判断根的孩子到底是左孩子还是右孩子。

比如先序序列1，5，后序序列是5，1

我们只知道1是这棵树的根，但是我们不知道5是1的左孩子还是右孩子。

我们的中序序列是左中右，才可以明确的划分出左右子树，而先序后序不可以。

综上，只有，只含叶子结点或者同时有左右孩子的结点的树，才可以被先序序列后序序列确定唯一一棵树。

最后不断划分先序和后序序列完成重建。

[Link 1]: https://baike.baidu.com/item/%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86
[Link 2]: https://baike.baidu.com/item/%E9%98%9F%E5%88%97
[20181121154249618.png]: /images/20220415/f2f5c959913245b3bb8196bbf4c4ec82.png
[201811211543214.png]: /images/20220415/118c495be9ec4e19ab2a5c5c2ce9ceb3.png
[20181121154345209.png]: /images/20220415/3556baf7ab744936a1b822314f47d697.png
[20181121154451150.png]: /images/20220415/1fafc3f1dffe4d26915e4e0cc84fb8af.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70]: /images/20220415/5eee41bfa5c5434680d1ed70708b8d92.png
[20181121154713894.png]: /images/20220415/63a228fc82514d22b60eb3f070c86689.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70 1]: /images/20220415/d497fd762e3d46cca9b8eb7522506c52.png