已知某二叉树的后序遍历序列是dabec中序遍历序列是debac1画出此二叉树的结构;
a
/ \
b c
/ \
d e
(2)说明如何通过后序遍历序列和中序遍历序列重建二叉树。
对于一棵二叉树,其后序遍历序列的最后一个元素一定是根节点,而在中序遍历序列中,根节点左边的元素都属于左子树,右边的元素都属于右子树。因此,我们可以通过后序遍历序列确定根节点,再在中序遍历序列中找到根节点,并确定左右子树的大小,递归地重建左右子树。
具体步骤如下:
- 后序遍历序列的最后一个元素d是根节点,根据中序遍历序列可知d的左边是左子树,右边是右子树;
- 在后序遍历序列中找到左子树的后序遍历序列eb,其顺序即为左子树遍历的顺序;
- 在中序遍历序列中找到左子树的中序遍历序列de,其顺序即为左子树遍历的顺序;
- 递归地重建左子树,返回左子树的根节点b;
- 在后序遍历序列中找到右子树的后序遍历序列c,其顺序即为右子树遍历的顺序;
- 在中序遍历序列中找到右子树的中序遍历序列ac,其顺序即为右子树遍历的顺序;
- 递归地重建右子树,返回右子树的根节点c;
- 将根节点d与左右子树b和c连接起来,得到完整的二叉树。
重建二叉树的过程可以用递归实现,具体实现见代码:
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(inorder, postorder):
if not inorder or not postorder:
return None
root_val = postorder[-1]
root = TreeNode(root_val)
# 找到根节点在中序遍历序列中的位置
idx = inorder.index(root_val)
# 递归地重建左右子树
root.left = buildTree(inorder[:idx], postorder[:idx])
root.right = buildTree(inorder[idx+1:], postorder[idx:-1])
return root
该函数接受中序遍历序列和后序遍历序列,返回重建的二叉树的根节点
原文地址: https://www.cveoy.top/t/topic/eFkV 著作权归作者所有。请勿转载和采集!