剑指Offer33-二叉搜索树的后序遍历序列

剑指Offer33-二叉搜索树的后序遍历序列

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树:


     5

    / \

   2   6

  / \

 1   3

示例 1:


输入: [1,6,3,2,5]

输出: false

示例 2:


输入: [1,3,2,6,5]

输出: true

提示:

  1. 数组长度 <= 1000

来源:力扣(LeetCode)

链接:力扣

一解

科普分治

使用递归分治法,什么是分治?即分而治之:

  1. 问题可被分解成若干子问题

  2. 子问题的解可合并为该问题的解

  3. 各个子问题独立,即子问题间不包含公共子问题

若只满足条件1,2:


1 

  \

    贪心算法或动态规划

  /

2

若三条都满足,可采用分治:


1 

   \

2  - 分治

   /

3

  • 二叉搜索树:左子树所有节点的值 < 根节点的值 < 右子树所有节点的值

  • 后序遍历:遍历顺序[左子树|右子树|根节点]

[1, 3, 2, 6, 5]为例:

分成两个子问题[1, 3, 2][6]

后续类似,不再演示。


class Solution:

    def verifyPostorder(self, postorder: List[int]) -> bool:

        def recur(i, j):

            if i >= j: return True

            p = i

            while postorder[p] < postorder[j]: p += 1

            m = p

            while postorder[p] > postorder[j]: p += 1

            return j == p and recur(i, m - 1) and recur(m, j - 1)

        return recur(0, len(postorder) - 1)