有了域名自己电脑怎么做网站,网站做锚点,广告设计与制作专业认识,手机直播软件1.题目描述 给定一个二叉树根节点#xff0c;请你判断这棵树是不是二叉搜索树。 二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。 例#xff1a; 图1 图2 数据范围#xff1a;节点数量满足 1≤#x1d45b;≤104 1≤n≤104…1.题目描述 给定一个二叉树根节点请你判断这棵树是不是二叉搜索树。 二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。 例 图1 图2 数据范围节点数量满足 1≤≤104 1≤n≤104 节点上的值满足 −231≤≤231−1 −231≤val≤231−1 示例1 输入 {1,2,3} 返回值 false说明 如题面图1 示例2 输入 {2,1,3} 返回值 true说明 如题面图2 2.解题思路
定义一个成员变量pre用于记录中序遍历时当前访问结点的前一个结点的值因为二叉搜索树的中序遍历是按升序排列的。我们只需要对比每一个访问结点的值和它前一个结点的值的大小关系即可如果不满足升序的要求时就无需再继续遍历了提前return即可。
3.代码实现
import java.util.*;/** public class TreeNode {* int val 0;* TreeNode left null;* TreeNode right null;* public TreeNode(int val) {* this.val val;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param root TreeNode类 * return bool布尔型*/public int pre Integer.MIN_VALUE;public boolean flag true;public boolean isValidBST (TreeNode root) {// write code heredfs(root);return flag;}public void dfs(TreeNode node) {if (flag false || node null) return;dfs(node.left);if (node.val pre) {pre node.val;} else {flag false;return;}dfs(node.right);}
}
