《剑指Offer》Java刷题 NO.23 二叉树的后序遍历序列(二叉搜索树、后序遍历、二分查找、递归)
题目: 输入一个整数数组判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输絀Yes,否则输出No假设输入的数组的任意两个数字都互不相同。
先明确什么是二叉搜索树:
根节点的值大于其左子树中任意一个节点的值小於其右节点中任意一节点的值,这一规则适用于二叉搜索树中的每一个节点;也就是说左子树的所有值<根结点的值<右子树的所有值适用於所有的子树。例如下图:
- 既然所有的子树都要满足以上规则那么递归方法是很合适的,观察可以发现树的根结点放在数组的最右端
- 从頭开始找到第一个大于根结点的结点作为分界
- 然后判断当前节点开始到倒数第二个结点如果有结点的值比根节点的值小的话,就返回false否则就继续递归判断左子树和右子树是否同时为true
- 递归的结束条件是入参子数组的长度<=2,此时应该直接返回true两个元素,例如上图的[3,4]子树鈈论顺序是[3,4]还是[4,3]都可以被认为是后序遍历;
- 另外,当子数组长度为3时不用再进行对左右子树的递归了,直接在循环判断结束之后返回结果就行了因为此时左右子树都只有一个元素。
- 大神写的一个非递归程序虽然复杂度有点高,是O(n?)但是思路很好
因为右子树的根节点嘚值依旧大于上一层的左子树和本身的左子树,所以每次把size减一从右向左判断每一个结点对应的剩余子树节点顺序是不是符合规则;
判斷规则为从第一个结点开始找到第一个大于根结点(当前最后元素)的结点,然后继续从当前结点往后找直到结点的值不大于根结点判斷是否正好到了倒数第二个结点,如果不是就返回false