当前位置:网站首页>剑指 Offer 33. 二叉搜索树的后序遍历序列

剑指 Offer 33. 二叉搜索树的后序遍历序列

2022-08-06 07:57:35愈努力俞幸运

剑指 Offer 33. 二叉搜索树的后序遍历序列icon-default.png?t=M666https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/

后序遍历,左右根

二叉搜索树:任意一个节点,左子树的值小于根节点的值,根节点的值小于右子树的值.

和画二叉树的思想一样,

列表中最后一个点为根节点,然后划分出左右子树,

左右子树再去划分。

递归解析:
终止条件: 当i≥j ,说明此子树节点数量 ≤1 ,i==j节点数量为1,i>j说明这个区间是空的,即左子树或右子树为空(如输入【1,2,5,10,6,9,4,3】)无需判别正确性,因此直接返回 true ;
递推工作:
划分左右子树: 从左到右遍历后序遍历的 [i, j]区间元素,寻找第一个大于根节点 的节点,索引记为 m 。此时,可划分出左子树区间 [i,m-1] 、右子树区间 [m, j - 1]、根节点索引j ,即每个区间最后一个点为根节点。
判断是否为二叉搜索树:
左子树区间 [i, m - 1]内的所有节点都应 < postorder[j] 
右子树区间 [m, j-1] 内的所有节点都应 >postorder[j]postorder[j] 。实现方式为遍历,当遇到 postorder[j]≤postorder[j] 的节点则跳出;若提前跳出,说明右子区间有比根节点值小的不符合二叉搜索树,则可通过 p == j判断是否为二叉搜索树。
返回值: 所有子树都需正确才可判定正确,因此使用 与逻辑符&& 连接。
p == j: 判断 此树 是否正确。
recur(i, m - 1): 判断 此树的左子树 是否正确。
recur(m, j - 1): 判断 此树的右子树 是否正确。

 

class Solution:
    def verifyPostorder(self, postorder):
        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 p==j and recur(i,m-1) and recur(m,j-1)
        return recur(0,len(postorder)-1)
a=Solution()
print(a.verifyPostorder([1,6,3,2,5]))

原网站

版权声明
本文为[愈努力俞幸运]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_37891604/article/details/126150913

随机推荐