二叉搜索树的后序遍历序列 题目描述 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 方法一（递归） 后续遍历得到的序列中最后一个素一定是树的根节点的值。数组中前面的数字可以分为两部分：左子树的值序列和右子树的值序列。左子树值都小于根节点值，右子树值都大于根节点值。 确定了左子树值和右子树值的序列，还是按上面的方法确定对应的子树的结构，这是一个递归的过程。如果递归过程中发现其右子序列中有值小于根值，那么这不是一个后序序列。 方法二（非递归） 非递归也是一个基于递归的思想： 左子树一定比右子树小，因此去掉根后，数字分为left，right两部分，right部分的最后一个数字是右子树的根，它比左子树所有值大，因此我们可以每次只看有子树是否符合条件即可。即使到达了左子树，左子树也可以看出由左右子树组成的树还像右子树那样处理。对于右子树，左子树的所有值都比右子树的根小可以暂时把他看出右子树的左子树，只需看看右子树的右子树是否符合要求即可。
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/88621.html
