面试题33. 二叉搜索树的后序遍历序列

https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/

这个题没啥好说的,就是靠思路,因为是后序遍历,数组最右边的一定是根节点,我们先向前找比根节点小的第一个数。那么这个数以及其左手边就是左子树,这个数右边到倒数第二个数就是右子树,然后我们创建一个helper方法,如果左子树中有比根节点大的,返回false,右子树中有比根节点小的,同样返回false,否则的话就一直递归下去知道数组长度小于2。代码如下:

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if(postorder.length < 2){
            return true;
        }
        int last = postorder.length - 1;
        int i = last;
        for(; i >=0; i--){
            if(postorder[i] < postorder[last]){
                break;
            }
        }
        return verify(Arrays.copyOfRange(postorder,0,i+1), Integer.MIN_VALUE, postorder[last]) && verify(Arrays.copyOfRange(postorder,i+1,last), postorder[last], Integer.MAX_VALUE);
    }

    private boolean verify(int[] postorder, int min, int max){
        if(postorder.length < 2){
            return true;
        }
        int last = postorder.length - 1;
        int i = last;
        for(; i >=0; i--){
            if(postorder[i] > max || postorder[i] < min){
                return false;
            }
            if(postorder[i] < postorder[last]){
                break;
            }
        }
        return verify(Arrays.copyOfRange(postorder,0,i+1), Integer.MIN_VALUE, postorder[last]) && verify(Arrays.copyOfRange(postorder,i+1,last), postorder[last], Integer.MAX_VALUE);
    }
}

 

上一篇:[LeetCode] 590. N-ary Tree Postorder Traversal


下一篇:Kubernetes plugin for Jenkins