遍历序列还原二叉树

SenZyo

2020-05-23 约 1482 字

1 题目

一棵二叉树的前序遍历序列为ABDHEICFG, 中序遍历序列为HDBEIACGF, 后序遍历序列为HDIEBGFCA。

2 知识点

必须已知二叉树的中序遍历序列, 才能唯一确定这棵二叉树, 题目一定会给出中序遍历序列。
前序遍历序列的第一个节点一定是二叉树的根节点, 比如节点A。
后序遍历序列的最后一个节点一定是二叉树的根节点, 比如节点A。
中序遍历序列中, 左子树节点一定在根节点的左侧, 比如HDBEI都在A的左侧；右子树节点同理。这样可避免画错二叉树。

3 正规解法

3.1 由前序和中序遍历序列求二叉树

由前序遍历序列ABDHEICFG可知根节点为A, 又因中序遍历序列HDBEIACGF中, HDBEI都在A的左侧, 可知HDBEI都是A的左子树节点, 同理CGF都是A的右子树节点。
```
 graph TB
     A((A)) --- HDBEI
     A --- CGF
```
对于前序遍历序列中BDHEI这棵子树, B是根节点, 由中序遍历序列HDBEI可知HD是B的左子树节点, EI是B的右子树节点。
```
 graph TB
     A((A)) --- B((B)) --- HD
     B --- EI
     A --- CGF
```
对于前序遍历序列中DH这棵子树, D是根节点, 由中序遍历序列HD可知H是D的左子树节点。同理, 对于前序遍历序列中EI这棵子树, E是根节点, 由中序遍历序列EI可知I是E的右子树节点。
```
graph TB
    A((A)) --- B((B)) --- D((D)) --- H((H))
    D ~~~ n1(( ))
    style n1 opacity:0
    B --- E((E)) ~~~ n2(( ))
    style n2 opacity:0
    E --- I((I))
    A --- CGF
```

对于前序遍历序列中CFG这棵子树, C是根节点, 由中序遍历序列CGF可知GF是C的右子树节点。

graph TB
    A((A)) --- B((B)) --- D((D)) --- H((H))
    D ~~~ n1(( ))
    style n1 opacity:0
    B --- E((E)) ~~~ n2(( ))
    style n2 opacity:0
    E --- I((I))
    A --- C((C)) ~~~ n3(( ))
    style n3 opacity:0
    C --- GF

对于前序遍历序列中FG这棵子树, F是根节点, 由中序遍历序列GF可知G是F的左子树节点。得到答案:

graph TB
    A((A)) --- B((B)) --- D((D)) --- H((H))
    D ~~~ n1(( ))
    style n1 opacity:0
    B --- E((E)) ~~~ n2(( ))
    style n2 opacity:0
    E --- I((I))
    A --- C((C)) ~~~ n3(( ))
    style n3 opacity:0
    C --- F((F)) --- G((G))
    F ~~~ n4(( ))
    style n4 opacity:0

3.2 由后序和中序遍历序列求二叉树

由后序遍历序列HDIEBGFCA可知根节点为A, 又因中序遍历序列HDBEIACGF中, HDBEI都在A的左侧, 可知HDBEI都是A的左子树节点, 同理CGF都是A的右子树节点。
```
 graph TB
     A((A)) --- HDBEI
     A --- CGF
```
对于后序遍历序列中HDIEB这棵子树, B是根节点, 由中序遍历序列HDBEI可知HD是B的左子树节点, EI是B的右子树节点。
```
 graph TB
     A((A)) --- B((B)) --- HD
     B --- EI
     A --- CGF
```
对于后序遍历序列中HD这棵子树, D是根节点, 由中序遍历序列HD可知H是D的左子树节点。同理, 对于后序遍历序列中IE这棵子树, E是根节点, 由中序遍历序列EI可知I是E的右子树节点。
```
graph TB
    A((A)) --- B((B)) --- D((D)) --- H((H))
    D ~~~ n1(( ))
    style n1 opacity:0
    B --- E((E)) ~~~ n2(( ))
    style n2 opacity:0
    E --- I((I))
    A --- CGF
```

对于后序遍历序列中GFC这棵子树, C是根节点, 由中序遍历序列CGF可知GF是C的右子树节点。

graph TB
    A((A)) --- B((B)) --- D((D)) --- H((H))
    D ~~~ n1(( ))
    style n1 opacity:0
    B --- E((E)) ~~~ n2(( ))
    style n2 opacity:0
    E --- I((I))
    A --- C((C)) ~~~ n3(( ))
    style n3 opacity:0
    C --- GF

对于后序遍历序列中GF这棵子树, F是根节点, 由中序遍历序列GF可知G是F的左子树节点。

graph TB
    A((A)) --- B((B)) --- D((D)) --- H((H))
    D ~~~ n1(( ))
    style n1 opacity:0
    B --- E((E)) ~~~ n2(( ))
    style n2 opacity:0
    E --- I((I))
    A --- C((C)) ~~~ n3(( ))
    style n3 opacity:0
    C --- F((F)) --- G((G))
    F ~~~ n4(( ))
    style n4 opacity:0

4 奇技淫巧

画一张表, 在第一列, 从上到下填入前序遍历序列 (或者从下到上填入后序遍历序列)。
在第一行, 从左到右填入中序遍历序列。
当行与列的节点相同时, 即确定该节点位置, 最后按照位置关系将节点连线得到二叉树。
连接时, 注意核实各节点相对于其父节点的左右位置。
中序遍历序列中, 左子树节点一定在根节点的左侧, 比如HDBEI都在A的左侧；右子树节点同理。

前序和中序	H	D	B	E	I	A	C	G	F
A						A
B			B
D		D
H	H
E				E
I					I
C							C
F									F
G								G

后序和中序	H	D	B	E	I	A	C	G	F
A						A
C							C
F									F
G								G
B			B
E				E
I					I
D		D
H	H

得到答案:

graph TB
    A((A)) --- B((B)) --- D((D)) --- H((H))
    D ~~~ n1(( ))
    style n1 opacity:0
    B --- E((E)) ~~~ n2(( ))
    style n2 opacity:0
    E --- I((I))
    A --- C((C)) ~~~ n3(( ))
    style n3 opacity:0
    C --- F((F)) --- G((G))
    F ~~~ n4(( ))
    style n4 opacity:0

目录

目录