3.2.22

上次更新:2019-10-06
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

这里的前驱和后继指的是二叉树中序遍历序列里结点的前驱和后继。

由于二叉搜索树的性质,它的中序遍历序列是递增有序的。
因此一个结点如果有左子树,要么前驱就是左子树中最大的结点(最右侧);
同理结点如果有右子树,要么后继就是右子树中最小的结点(最左侧)。

于是结点的前驱不会有右子节点,后继不会有左子节点,得证。

上一题 下一题