题目地址(33. 二叉搜索树的后序遍历序列)

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

题目描述

  1. 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
  5. 参考以下这颗二叉搜索树：
  7.      5
  8.     / \
  9.    2   6
  10.   / \
  11.  1   3
  13. 示例 1：
  15. 输入: [1,6,3,2,5]
  16. 输出: false
  18. 示例 2：
  20. 输入: [1,3,2,6,5]
  21. 输出: true
  25. 提示：
  27. 数组长度 <= 1000

前置知识


公司

  • 暂无

思路

二叉搜索树一个特性就是：左子树比根节点小，右子树比根节点大
只要找到左右子树的分界点，然后递归的去判定就好了
中途有任何不满足的就直接返回false就ok

关键点

  • 二叉搜索树中根节点的值大于左子树中的任何一个节点的值，小于右子树中任何一个节点的值，子树也是

代码

  • 语言支持：Java

Java Code:

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return loop(postorder, 0, postorder.length - 1);
    }

    private boolean loop(int[] postorder, int left, int right) {
        //递归终止条件 递归到最后还没有返回false就是对的
        if (left >= right) {
            return true;
        }
        //根节点的值
        int rootValue = postorder[right];
        int k = left;
        //找到右边子树开始的节点
        while (postorder[k] < rootValue) {
            k++;
        }
        //左子树都小于根节点 而上方的while就已经完成了筛选
        //判断右子树的数字是否都大于根节点
        for (int i = k; i < right; i++) {
            if (postorder[i] < rootValue) {
                return false;
            }
        }
        //递归判断左子树
        if (!loop(postorder, left, k - 1)) {
            return false;
        }
        //递归判断右子树
        if (!loop(postorder, k, right - 1)) {
            return false;
        }
        //没问题就返回true
        return true;
    }
}

复杂度分析

令 n 为数组长度。

  • 时间复杂度：剑指 Offer 33. 二叉搜索树的后序遍历序列 - 图1#card=math&code=O%28n%29&id=o9fUp)
  • 空间复杂度：剑指 Offer 33. 二叉搜索树的后序遍历序列 - 图2#card=math&code=O%28n%29&id=xIeET)