题目描述
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
样例
-
样例1：
输入:
2
/ \
1 3
输出: true -
样例2
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。根节点的值为 5 ，但是其右子节点值为 4 。
题目评估
知识点：DFS、树、递归
难度：中等
题目分析
一个二叉排序树的中序遍历一定是升序的，所以我们直接中序遍历，检验得到的排序是否升序即可，但是我们不用存储这个排序数组，只要记录一个数字，将下轮得到的数字和上个数字进行比较即可。
Java代码题解
递归DFS
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
long beforeVal = Long.MIN_VALUE; // 定义一个long型记录上一个节点的值
public boolean isValidBST(TreeNode root) {
if (root == null) { // 如果当前节点为null直接返回true
return true;
}
boolean leftFlag = isValidBST(root.left); // 递归左子树
if (root.val <= beforeVal) { // 如果当前节点的值小于上一个中序遍历的值直接返回false
return false;
}
beforeVal = root.val; // 将本次节点的值记录到beforeVal
boolean rightFlag = isValidBST(root.right); // 遍历右子树
return leftFlag && rightFlag;
}
}
复杂度分析：
中序遍历时间复杂度为O(n)
递归调用使用栈空间，空间复杂度为O(n)
非递归DFS
//import java.util.Stack;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
long beforeVal = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
// 定义一个栈用来存储未中序遍历过的左子树
Stack<TreeNode> stack = new Stack<TreeNode>();
long before = Long.MIN_VALUE; // 定义一个数字用来存储上一个中序遍历的值
while (root != null || !stack.empty()) { // 栈不空 树不空 就一直运行
while (root != null) { // 把左子树存到栈中
stack.push(root);
root = root.left;
}
// 遍历到无左子树的节点后弹出无左子树的节点
root = stack.pop();
if (root.val <= beforeVal) { // 把它和中序遍历排序上一个数字比较
return false; // 如果小于等于上一个数字直接返回false
}
beforeVal = root.val; // 把本次数字赋值为上一个数字
root = root.right; // 同样的操作处理这个节点的右子树
}
return true;
}
}
复杂度分析：
中序遍历一遍顺序遍历，时间复杂度为O(n)
在遍历的过程中使用栈做辅助存储，空间复杂度为O(n)