当前位置:网站首页>【二叉树】二叉搜索树的后序遍历序列

【二叉树】二叉搜索树的后序遍历序列

2022-08-10 19:06:00 豪冷啊

0x00 题目

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


0x01 思路

后序遍历的结果是:左,右,中
最后一个是节点
子树的所有节点都 大于 根节点
找到第一个大于 根节点的 索引
即可区分左右子树


0x02 解法

语言:Swift

树节点:TreeNode

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

解法:

func verifyPostorder(_ postorder: [Int]) -> Bool {
    func verify(_ i: Int, _ j: Int) -> Bool {
        // 说明此子树节点数量 ≤ 1 ,无需判断,直接 true
        if i >= j { return true }
        
        // 寻找 第一个大于根节点 的节点
        // 即左子树 都要小于 要节点
        var p = i
        while postorder[p] < postorder[j] {
            p += 1
        }
        
        // 右子树都大于根节点
        let m = p
        while postorder[p] > postorder[j] {
            p += 1
        }
        
        // 不再大于时,说明索引应该等于 根节点
        let b1 = (p == j)
        // 验证左子树
        let b2 = verify(i, m-1)
        // 验证右子树
        let b3 = verify(m, j-1)
        
        return b1 && b2 && b3
    }
    
    return verify(0, postorder.count-1)
}


0x03 我的小作品

欢迎体验我的作品之一:小五笔
五笔学习好帮手~
App Store 搜索即可~


原网站

版权声明
本文为[豪冷啊]所创,转载请带上原文链接,感谢
https://blog.csdn.net/xjh093/article/details/126268620