二叉树重建:根据前序遍历和中序遍历结果画出二叉树
已知一棵二叉树的前序遍历结果序列是'ABDEGJCFHIK',中序遍历的结果是'DBGJEAHFKIC',请画出这棵二叉树
解答:
根据前序遍历和中序遍历的结果,可以唯一确定一棵二叉树。重建二叉树的步骤如下:
- 找到根节点: 前序遍历的第一个节点为根节点,即 'A'。
- 在中序遍历中找到根节点: 在中序遍历中找到根节点 'A',并将中序遍历序列划分为左右子树:
- 左子树:'DBGJE'
- 右子树:'HFKIC'
- 递归重建左右子树:
- 左子树的前序遍历序列为 'BDEGJ',中序遍历序列为 'DBGJE',递归重建左子树。
- 右子树的前序遍历序列为 'CFHIK',中序遍历序列为 'HFKIC',递归重建右子树。
最终重建的二叉树如下:
A
/ \
B C
/ \ / \
D E F G
/ / \
J H I
\
K
注: 这棵二叉树的形态不唯一,但前序和中序遍历的结果是唯一的。
原文地址: https://www.cveoy.top/t/topic/mQah 著作权归作者所有。请勿转载和采集!