【LeetCode算法修炼+动画演示】【二叉树的遍历】——98.验证二叉搜索树

65 阅读 0 评论 43 点赞

我是靠谱客的博主感动西牛，最近开发中收集的这篇文章主要介绍【LeetCode算法修炼+动画演示】【二叉树的遍历】——98.验证二叉搜索树，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

98.验证二叉搜索树

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

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

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

输入:
    2
   / 
  1   3
输出: true

示例 2:

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

要点

二叉搜索树的左结点必定小于右结点。
形成夹角的节点需要判断与上界下界的关系

98.验证二叉搜索树

递归

递归判断每一个结点是否符合在

代码片段

func isValidBST(root *TreeNode) bool {
	return isValidBSTHelper(root, nil, nil)
}

func isValidBSTHelper(root *TreeNode, lower, upper *int) bool {
	if root == nil {
		return true
	}
	val := root.Val
	if lower != nil && val <= *lower {
		return false
	}
	if upper != nil && val >= *upper {
		return false
	}

	if !isValidBSTHelper(root.Right, &val, upper) {
		return false
	}

	if !isValidBSTHelper(root.Left, lower, &val) {
		return false
	}
	return true
}

代码解释

我们需要仔细的分析一下动画演示，在验证整个二叉搜索树的过程中，大概有两种情况

结点顺着最边缘的时候只会对应一个上界或者下界(这里以动画的结构做演示)，
```
	9
   / 
  3   20
       
       22
```

结点存在夹角,这里 15被 9跟20夹在中间

在判断15这个结点的时候就不能单纯判断是否是小于根结点20，还要确认是否大于9，如果不大于9的话就不是一棵二叉搜索树了。所以在整个验证过程需要记录当前结点上界和下界。

BSF广度优先遍历

将下一层的每个节点对应的上界跟下界记录起来，类似系统调用栈保留每层调用的变量。

代码片段

func isValidBST(root *TreeNode) bool {
	if root == nil {
		return true
	}

	link := list.New()
	type tmp struct {
		node  *TreeNode
		lower int
		upper int
	}
	link.PushBack(tmp{node: root, lower: math.MinInt64, upper: math.MaxInt64})
	for link.Len() > 0 {
		node := link.Remove(link.Back()).(tmp)
		if node.node.Left != nil {
			if node.node.Left.Val >= node.node.Val || node.node.Left.Val <= node.lower {
				return false
			}
			link.PushBack(tmp{node: node.node.Left, lower: node.lower, upper: node.node.Val})
		}
		if node.node.Right != nil {
			if node.node.Right.Val <= node.node.Val || node.node.Right.Val >= node.upper {
				return false
			}
			link.PushBack(tmp{node: node.node.Right, lower: node.node.Val, upper: node.upper})
		}
	}
	return true
}