Jianbo Dai's

jz033.二叉搜索树的后序遍历序列

 
  • Jun 17, 2020

题目链接

嗯，试了一下，大概知道是分治的思路，但是好像总写不对递归终止的条件，写得比较繁琐。简单来说，在后序遍历得到的序列中，最后一个数字是树的根节点的值，除了最后一个节点的前面的数字也可以分成两部分：前一部分是左子树节点的只，它们都比根节点的值小；第二部分是右节点的值，它们都比根节点的值大。知道了这个特性，我们就可以继续递归地判断应该在某个子树里的数字是否是一个合格的序列。终止条件一下子不好想，下面代码里呈现的是：遍历数组，当数组中出现第一个数字大于等于根节点（也就是序列末位）的值时，我们就认为这个时刻是从左子树过渡到右子树的时刻；当继续向序列末尾遍历时，当出现第一个数字小于等于（正常情况下应该是等于，因为第二部分当数字应该都严格小于根节点）根节点时，我们认为走到了末尾。这时候的下标应该等于序列长度-1，否则说明序列中除了最后一个节点的数字没法恰好分成合格的两部分。这个算法的时间复杂度是O（N^2），空间复杂度是O（N）。

还有另外一种思路，就是利用单调栈。那怎么利用呢，我们注意到后序遍历的倒序【根节点｜右子树｜左子树】与先序遍历的镜像一样（先序遍历为【根节点｜左子树｜右子树】）。因此我们考虑逆序遍历后序遍历列表。当遍历时，对于相邻元素，有两种情况：当后一个元素大于前一个元素时，后一个元素必定是前一个元素的右子节点。当后一个元素小于前一个元素时，后一个元素必定是某个root根节点的左子节点，并且root节点为序列中该左子节点前的所有节点中值大于且接近该左子节点值的节点（因为root节点直接与该左子节点直接连接）。这个解法的时间复杂度为O（N）（O（2N))，空间复杂度为O（N）。

class Solution:

    def verifyPostorder1(self, postorder: [int]) -> bool:
        self.postorder = postorder
        return self.recur(0, len(postorder) - 1)

    def recur(self, i, j):
        if i >= j:
            return True
        p = i
        while self.postorder[p] < self.postorder[j]:
            p += 1
        m = p
        while self.postorder[p] > self.postorder[j]:
            p += 1
        return p == j and self.recur(i, m - 1) and self.recur(m, j - 1)

    def verifyPostorder2(self, postorder: [int]) -> bool:
        stack, root = [], float("+inf")
        for i in range(len(postorder) - 1, -1, -1):
            if postorder[i] > root:
                return False
            while (stack and postorder[i] < stack[-1]):
                root = stack.pop()
            stack.append(postorder[i])
        return True
Search