二叉搜索树的后序遍历序列(verifyPostorder) Leetcode 22

言简意赅的说明题意:

就是给你一个序列,让你判断一下该序列是不是一个二叉搜索树的后序遍历序列。

例如,给你一个序列: [1,6,3,2,5]

请判断是不是二叉搜索树的后序遍历序列。

来一个例子:序列

class Solution {
        public boolean verifyPostorder(int[] postorder) {
            return recur(postorder, 0, postorder.length - 1);//待判断序列,上标,下标
        }
        boolean recur(int[] postorder, int i, int j) {
            if(i >= j) return true;     //下标小于上标,则返回,也是一个递归出口

            int p = i;                  //从开始往后走
            while(postorder[p] < postorder[j]) {//找到第一个大于根的结点
                p++;
            }
            //从m往后都是右子树
            int m = p;
            while(postorder[p] > postorder[j]) {
                p++;
            }//找到不大于根的结点p
            return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
            //判断不大于根的结点是不是根结点本身 并且 判断左子树满不满足该条件 并且 右子树满不满足该条件
        }
    }

数组是[3,5,13,10,12,9]

    a) 根据数组拆分,第一个比9大的后面都是9的右子节点[13,10,12]。然后再拆分这个数组,12是根节点,
    b) 第一个比12大的后面都是12的右子节点[13,10],但我们看到10是比12小的,他不可能是12的右子节点,
    c) 所以我们能确定这棵树不是二叉搜索树。

上一篇:AR APP测试:现有工具简单调研


下一篇:JAVA基础代码分享--学生成绩管理