LeetCode 98 校验二叉搜索树

1 题目描述

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

假定一个二叉搜索树的定义为：

a）一个节点的左子树包含的节点的key小于该节点的key；

b）一个节点的右子树包含的节点的key大于该节点的key；

c）左右子树均须是二叉搜索树。

例子1：

    2
   / \
  1   3

输入：[2,1,3]

输出：true

例子2：

输入：[5,1,4,null,null,3,6]

输出：false

释义：根节点值为5，而右节点值为4，小于根节点值。

题目出处：LeetCode

2 解决思路

按照二叉搜索树定义，若对其进行先序遍历，则应满足节点key递增原则。

本文采用递归方式对二叉树进行先序遍历，使用一个变量记录上一个遍历到的节点的key，若当前key不大于上一个key，则退出遍历，返回false。

3 Golang实现代码

https://github.com/leileiluoluo/

func preOrderTraversal(root *TreeNode, preVal *int) bool {
    if nil == root {
        return true
    }
    ok := preOrderTraversal(root.Left, preVal)
    if !ok {
        return false
    }
    if root.Val <= *preVal {
        return false
    }
    *preVal = root.Val
    return preOrderTraversal(root.Right, preVal)
}

func isValidBST(root *TreeNode) bool {
    preVal := -(1 << 32)
    return preOrderTraversal(root, &preVal)
}

LeetCode 98 校验二叉搜索树

相关文章

评论