一棵二叉树的先序序列和后序序列正好相反,则二叉树高度等于其结点数
时间: 2023-08-10 21:34:06 浏览: 48
对于一棵二叉树,它的先序遍历序列的第一个结点是根节点,后序遍历序列的最后一个结点也是根节点。如果给定的先序序列和后序序列正好相反,那么该二叉树的根节点应该是后序序列的第一个结点,也是先序序列的最后一个结点。此时将先序序列和后序序列反转即可得到该二叉树的中序遍历序列。
对于一棵二叉树,其高度一定小于等于结点数。如果一棵二叉树高度等于结点数,那么它必须是一棵满二叉树,即所有非叶子结点都有两个子结点。因此,我们可以考虑构造一棵满二叉树,然后分别对其进行先序遍历、中序遍历和后序遍历,将先序序列和后序序列反转后比较,如果相同则说明该二叉树满足条件。
举个例子,假设我们要构造一个高度等于结点数的二叉树,其结点数为 $n=7$。我们可以按照以下方式构造:
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
这棵二叉树的先序遍历序列为 $[1, 2, 4, 5, 3, 6, 7]$,中序遍历序列为 $[4, 2, 5, 1, 6, 3, 7]$,后序遍历序列为 $[4, 5, 2, 6, 7, 3, 1]$。将先序序列和后序序列反转后得到 $[7, 6, 3, 5, 4, 2, 1]$,与原来的中序序列相同,因此该二叉树满足条件。
相关问题
一棵非空二叉树,若先序遍历与后序遍历的序列相反,则该二叉树所有结点均无左孩子。
这个说法是正确的。如果一棵二叉树的先序遍历和后序遍历序列恰好相反,那么可以推断出该二叉树所有结点均无左孩子。因为先序遍历是先遍历根结点,再遍历左子树和右子树,而后序遍历是先遍历左子树和右子树,再遍历根结点。如果一个结点有左孩子,那么在先序遍历序列中,它的左孩子会被先遍历,而在后序遍历序列中,它的左孩子会被后遍历,这两个序列不可能相反。因此,如果先序遍历和后序遍历序列相反,那么所有结点都没有左孩子。
一棵非空二叉树,若先序遍历与后序遍历的序列相反,则该二叉树所有结点均无右孩子。
这个说法是错误的。如果一棵二叉树的先序遍历和后序遍历序列恰好相反,不能推断出该二叉树所有结点均无右孩子。举个例子,下面这棵二叉树的先序遍历和后序遍历序列都是{1, 3, 2}和{3, 1, 2},但是它的根结点2有右孩子3。
```
2
\
3
/
1
```
因此,先序遍历和后序遍历序列相反并不能说明所有结点均无右孩子。