LeetCode - 98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法

swift

• 中序递归遍历
  通过中序递归遍历，得到递增的数组，遍历数组，判断是否为二叉搜索树

/**
    中序递归遍历
    */
    func isValidBST(_ root: TreeNode?) -> Bool {
        var result = [Int]()
        if root == nil {
            return true
        }
        // 二叉搜索树，中序遍历，遍历之后的数组为严格递增
        helper(root!, &result)
        // 判断数组是否严格递增
        for i in 0..<result.count-1 {
            if result[i] >= result[i+1] {
                return false
            }
        }
        return true
    }

    // 中序递归遍历 
    func helper(_ node: TreeNode?, _ result: inout [Int]) {
        if node == nil {
            return
        }
        helper(node?.left, &result)
        result.append(node!.val)
        helper(node?.right, &result)
    }

• 中序迭代
  二叉搜索树，中序遍历结果为递增，在迭代过程中直接判断前后的值

/**
    迭代中序遍历
    */
    func isValidBST(_ root: TreeNode?) -> Bool {
        var stack = [TreeNode]()
        var root = root
        // 中间变量保存上一个节点的值
        var minValue = Int.min
        while !stack.isEmpty || root != nil {
            while root != nil {
                stack.append(root!)
                root = root!.left
            }
            let current = stack.popLast()
            // 过程中直接判断
            if current!.val <= minValue {
                return false
            }
            minValue = current!.val
            root = current!.right
        }
        return true
    }

GitHub：https://github.com/huxq-coder/LeetCode
欢迎star