1. 首页
  2. 剑指offer经典面试题

第 33 题:二叉搜索树的后序遍历序列(递归、分治)

[剑指 Offer 第 2 版第 33 题] “二叉搜索树的后序遍历序列”做题记录

第 33 题:二叉搜索树的后序遍历序列(递归、分治)

传送门:二叉搜索树的后序遍历序列牛客网 online judge 地址

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。

如果是则返回 true,否则返回 false。

假设输入的数组的任意两个数字都互不相同。

样例:

输入:[4, 8, 6, 12, 16, 14, 10]

输出:true

分析:前提:数组中的数字各不相同。注意到题目中已经注明了:假设输入的数组的任意两个数字都互不相同

  • 根结点是后序遍历的最后一个元素,因此一定位于给定数组的最后一位;
  • 那么给定数组的最后一位就可以把这个数组分为两个部分,前半部分严格小于最后一个数,后半部分严格大于最后一个数;

根据以上两条就很容易写出递归的代码。

依据:后序遍历最后遍历到的一定是根结点。

注意:边界条件。

思想:分治。

Python 代码:

  class Solution:
        def verifySquenceOfBST(self, sequence):
            """
            :type sequence: List[int]
            :rtype: bool
            """
            # 先写特殊情况
            l = len(sequence)
            if l == 0:
                return False
            if l == 1:
                return True

            return self.__helper(sequence, 0, l - 1)

        def __helper(self, sequence, left, right):
            # 先写递归终止条件
            if left >= right:
                return True
            # 此时区间最右边的数作为标定元素
            pivot = sequence[right]
            # 设置一个遍历指针,把 [left, right -1] 这个区间里的元素全部看一遍

            # 正确的情况是:最右边的元素把前面的数组分成两部分:
            # 第 1 部分的元素全部严格小于最右边的元素
            # 第 2 部分的元素全部严格大于最右边的元素
            point = left
            while sequence[point] < pivot:
                point += 1
            # 此时 [left, point - 1] 中的元素都严格比最右边的元素小
            # 下面就依次验证后面的元素是不是都严格比最右边的元素大就好了
            mid = point - 1
            # 此后,所有的数都应该比 pivot 大
            while point < right:
                if sequence[point] > pivot:
                    point += 1
                else:
                    return False
            return self.__helper(sequence, left, mid) and self.__helper(sequence, mid + 1, right - 1)

Python 代码:分治法

  class Solution:
        def verifySquenceOfBST(self, sequence):
            """
            :type sequence: List[int]
            :rtype: bool
            """
            if not sequence: return False

            root = sequence[-1]
            for i in range(len(sequence)):
                if sequence[i] > root:
                    break

            for j in range(i,len(sequence)):
                if sequence[j] < root:
                    return False

            left = True
            if i > 0:
                left = self.verifySquenceOfBST(sequence[:i])

            right = True
            if i < len(sequence)-1:
                right = self.verifySquenceOfBST(sequence[i:-1])

            if left and right: return True
            return False

Java 代码:

  • 根结点是后序遍历的最后一个元素,因此一定位于给定数组的最后一位。
  • 那么给定数组的最后一位就可以把这个数组分为两个部分,前半部分小于最后一个数,后半部分大于最后一个数。
  • 根据以上两条就很容易写出递归的代码。

Java 代码:

  public class Solution {
        public boolean VerifySquenceOfBST(int[] sequence) {
            int len = sequence.length;
            if (len == 0) {
                return false;
            }
            if (len == 1) {
                return true;
            }
            int l = 0;
            int r = len - 1;
            while (l <= r) {
                int mid = judgeBST(sequence, l, r);
                if (mid == -1) {
                    return false;
                }
                // 注意考虑数组下标越界的问题
                // return (mid > 1 ? judgeBST(sequence, l, mid - 1) != -1 : true) && judgeBST(sequence, mid, r) != -1;
                return (mid <= 1 || judgeBST(sequence, l, mid - 1) != -1) && judgeBST(sequence, mid, r) != -1;
            }
            return true;
        }

        // mid 以及 mid 以后的数子都小于 arr[r]
        private int judgeBST(int[] arr, int l, int r) {
            int p = arr[r];
            int i = l;
            int mid;
            // 5,4,3,2,1
            while (arr[i] < p) {
                i++;
            }
            mid = i;
            while (arr[i] > p && i < r) {
                i++;
            }
            // 如果遍历到末尾了,就说明,在这一层,是可以构成 BST 的
            if (i == r) {
                return mid;
            }
            return -1;
        }

        public static void main(String[] args) {
            // int[] nums1 = {5, 7, 6, 9, 11, 10, 8};
            int[] nums = {5, 4, 3, 2, 1};
            Solution solution = new Solution();
            boolean verifySquenceOfBST = solution.VerifySquenceOfBST(nums);
            System.out.println(verifySquenceOfBST);
        }
    }

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:第 33 题:二叉搜索树的后序遍历序列(递归、分治)

链接:https://www.javajike.com/article/3258.html

« [剑指 Offer 第 2 版第 8 题] “二叉树的下一个结点”做题记录
[剑指 Offer 第 2 版第 10 题] “矩形覆盖”做题记录»

相关推荐

QR code