高频算法面试题（三十八）- 判断一棵树是否为二叉搜索树

发表于

「这是我参与11月更文挑战的第 23 天，活动详情查看：2021最后一次更文挑战」

刷算法题，从来不是为了记题，而是练习把实际的问题抽象成具体的数据结构或算法模型，然后利用对应的数据结构或算法模型来进行解题。个人觉得，带着这种思维刷题，不仅能解决面试问题，也能更多的学会在日常工作中思考，如何将实际的场景抽象成相应的算法模型，从而提高代码的质量和性能

判断一棵树是否为二叉搜索树

题目来源：LeetCode-98. 验证二叉搜索树

题目描述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

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

示例

示例 1

1.png

1
2
ini复制代码输入：root = [2,1,3]
输出：true

示例 2

2.png

1
2
3
csharp复制代码输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4

提示：

  • 树中节点数目范围在[1, 10^4] 内
  • 2^31 <= Node.val <= 2^31 - 1

解题

解法一：递归

思路

如果一个结点的左右子树是二插搜索树，那么它本身也是二插搜索树。根据题目中给的说明，一个二插搜索树满足这样的条件：

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

这里有一个误区，代码容易写成仅判断了根节点和它左右节点组成的子树是不是平衡二叉树。这样其实是不对，比如这样写就是不对的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
go复制代码func isValidBST(root *TreeNode) bool {
	if root == nil {
		return true
	}

	return isValid(root)
}

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

	if root.Left == nil && root.Right == nil {
		return true
	}

	if root.Left != nil && root.Left.Val >= root.Val {
		return false
	}

	if root.Right != nil && root.Right.Val <= root.Val  {
		return false
	}

	return isValid(root.Left) && isValid(root.Right)
}

比如这种情况，上边的代码就会不通过

3.png

代码只判断出来了5、4、6和6、3、7都是二插搜索树，但是整体并不是一个二插搜索树

因此，需要换种思路。很容易想到使用递归，假设root为根的子树，应该判断子树中的所有结点都在(min，max)这个区间内（开区间），如果root的值不在(min，max)这个区间内，说明不满足二插搜索树的条件，直接返回即可。否则就继续遍历左右子树

在递归左子树的时候，上边界的max，就应该替换成root.Val（也就是当前节点的值）。同理，在递归右子树的时候，下边界的min，就应该替换成root.Val

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
arduino复制代码func isValidBST(root *TreeNode) bool {
	return isValid(root, math.MinInt64, math.MaxInt64)
}

func isValid(root *TreeNode, min, max int) bool {
	if root == nil {
		return true
	}

	if root.Val <= min || root.Val >= max {
		return false
	}

	// isValid(root.Left, min, root.Val) 左子树的值，都应该比当前这个节点小，因此它的下边界的值应该是当前结点的值
	//isValid(root.Right, root.Val, max) 右子树的值，都应该比当前这个节点大，因此它的上边界的值应该是当前结点的值
	return isValid(root.Left, min, root.Val) && isValid(root.Right, root.Val, max)
}

解法二：中序遍历

思路

因为我们知道，对于一颗二插搜索树，它的中序遍历，可以升序的打印出所有节点的值。利用这一特性来进行解题，因为在遍历的过程中，需要比较当前结点的值，是否大于前一个结点的值，因此递归实现中序遍历，不好加这层判断，所以，需要使用中序遍历的非递归遍历

我前边有篇文章，详细的分享了树的前、中、后序遍历的递归和非递归遍历，以及层序遍历，如果你不是很了解，可以移步这里。二叉树的变量，是所有树的算法题的基础，你会发现，所有树的题，都是遍历树的变形题，只是在遍历过程中增加了一些操作

二叉树的中序非递归遍历，需要借助栈，因此用栈来实现，具体代码如下

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
go复制代码//中序遍历实现
func isValidBST2(root *TreeNode) bool {
	nodeStack := []*TreeNode{}
	preNodeVal := math.MinInt64
	for len(nodeStack) != 0 || root != nil {
		for root != nil {
			nodeStack = append(nodeStack, root)
			root = root.Left
		}
		root = nodeStack[len(nodeStack)-1]
		nodeStack = nodeStack[:len(nodeStack)-1]
		if root.Val <= preNodeVal {
			return false
		}
		preNodeVal = root.Val
		root = root.Right
	}

	return true
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%