网站搭建本地环境_网站建设推广优化公司_关键词歌词_广州30万人感染

问题背景

给你一个二叉树的根节点 $root$，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：

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

数据约束

• 树中节点数目范围在 $[1,10^4]$ 内
• $-2^{31}\le Node.val\le 2^{31}-1$

解题过程

二叉搜索树的判定会涉及到不同子树的节点之间的比较，总体来说根据遍历顺序的不同有三种常规解法：

• 先序遍历，递归方法中维护当前节点的可能值范围，递归过程中判断每个节点是否在合法范围内即可。
• 中序遍历，定义一个变量来记录节点值的下界，可以不定义新的方法。
• 后序遍历，递归时维护每棵子树上的最大最小值，以此来判断不同子树上有没有范围交叉的情况出现。

注意这题节点值可能取到整型最大值，把数值处理的范围扩大到长整型来避免出现问题。

具体实现

先序遍历

/*** 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 {public boolean isValidBST(TreeNode root) {// 初始状态下根节点的值没有任何限制return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);}private boolean isValidBST(TreeNode root, long left, long right) {if(root == null) {return true;}long cur = root.val;// 左子树上节点值的范围应该在 (left, cur) 内// 右子树上节点值的范围应该在 (cur, right) 内return left < cur && cur < right && isValidBST(root.left, left, cur) && isValidBST(root.right, cur, right);}
}

中序遍历

/*** 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 {// pre 表示当前节点值的下界private long pre = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root == null) {return true;}// 先递归判断左子树是否是二叉搜索树，再判断当前节点是否满足二叉搜索树的条件if(!isValidBST(root.left) || root.val <= pre) {return false;}// 左子树和当前节点判断完成之后，后续节点的下界至少是当前节点值pre = root.val;// 最后递归判断右子树return isValidBST(root.right);}
}

后序遍历

/*** 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 {public boolean isValidBST(TreeNode root) {// 根节点上实际的最小值不可能是长整型的最小值，以此来判断是否满足条件return dfs(root)[0] != Long.MIN_VALUE;}private long[] dfs(TreeNode root) {// 节点为空时认为当前子树是二叉搜索树，用不可能的取值范围表示空if(root == null) {return new long[] {Long.MAX_VALUE, Long.MIN_VALUE};}long[] left = dfs(root.left); // 递归得到左子树的节点值范围long[] right = dfs(root.right); // 递归得到右子树的节点值范围long cur = root.val;// 如果当前节点值小于左子树的最大值或者大于右子树的最小值，说明出现交叉，返回非法结果if(cur <= left[1] || cur >= right[0]) {return new long[] {Long.MIN_VALUE, Long.MAX_VALUE};}// 根据之前的记录和当前节点值，返回当前子树上节点值的取值范围return new long[] {Math.min(left[0], cur), Math.max(right[1], cur)};}
}