【LeetCode】剑指 Offer 33. 二叉搜索树的后序遍历序列

【LeetCode】剑指 Offer 33. 二叉搜索树的后序遍历序列 【LeetCode】剑指 Offer 33. 二叉搜索树的后序遍历序列

文章目录

• 【LeetCode】剑指 Offer 33. 二叉搜索树的后序遍历序列

package offer;

public class Solution33 {
    public static void main(String[] args) {
        int[] postorder = {1,6,3,2,5};
        Solution33 solution = new Solution33();
        System.out.println(solution.method(postorder));
    }

    private boolean method(int[] postorder){
        return recur(postorder, 0, postorder.length - 1);
    }

    private boolean recur(int[] postorder, int i, int j){
        if(i >= j) return true;
        int p = i;
        while(postorder[p] < postorder[j]) p++;
        int m = p;
        while (postorder[p] > postorder[j]) p++;
        return (p == j) && recur(postorder, i, m-1) && recur(postorder, m, j-1);
    }
}

//时间复杂度为 O(n^2)
//空间复杂度为 O(n)