简介

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

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

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

示例1:

输入:
    2
   / \
  1   3
输出: true

示例2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ,但是其右子节点值为 4 。

解题过程

首先,了解到二叉收索树,我们需要遍历整个树,检查 node.right.val > node.valnode.left.val < node.val 对每个结点是否成立。

二叉树
二叉树

但是这种方法并不总是正确。不仅右子结点要大于该节点,整个右子树的元素都应该大于该节点。例如:

二叉树
二叉树

因此,我们可以使用递归来实现,首先将结点的值与上界和下界(如果有)比较。然后,对左子树和右子树递归进行该过程。

图片
图片
图片
图片
图片
图片
图片
图片

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
	return helper(root, nil, nil)
}

func helper(node *TreeNode, lower, upper interface{}) bool {
	if node == nil {
		return true
	}
	
	val := node.Val

	if lower != nil && val <= lower.(int){
		return false
	}

	if upper != nil && val >= upper.(int) {
		return false
	}

	if !helper(node.Right,val,upper) {
		return false
	}

	if !helper(node.Left,lower,val) {
		return false
	}
	
	return true
}

复杂度分析

  • 时间复杂度 : O(N)。每个结点访问一次。
  • 空间复杂度 : O(N)。我们跟进了整棵树。