商务网站建设,简约个人网站,电商网站有哪些,小程序个人开发全过程验证二叉搜索树中等给你一个二叉树的根节点 root #xff0c;判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下#xff1a;节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。示例 1…验证二叉搜索树中等给你一个二叉树的根节点 root 判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。 示例 1输入root [2,1,3]输出true示例 2输入root [5,1,4,null,null,3,6]输出false解释根节点的值是 5 但是右子节点的值是 4 。题解中序遍历创建节点和list集合list集合用于节点遍历后值的存储声明一个中序遍历方法递归求解传入参数获取节点值遍历集合根据中序遍历性质如果找到前一个值大于后一个值说明该树不符合平衡二叉树的特点返回false,否则返回true。中序遍历左中右当前节点左右子树不为空时递归调用先递归遍历左子树节点在获取当前节点在递归遍历右子树节点/*** 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) {ListInteger list new ArrayList();infixOrder(root,list);System.out.println(list);boolean flag true;for (int i 1; i list.size(); i) {if(list.get(i-1) list.get(i)){flag false;System.out.println(flag);return flag;}}System.out.println(flag);return flag;}public void infixOrder(TreeNode root,ListInteger list){if(root ! null){if(root.left ! null){infixOrder(root.left,list);}list.add(root.val);if(root.right ! null){infixOrder(root.right,list);}}}
}
