【Hot100】LeetCode—98. 验证二叉搜索树

本文主要是介绍【Hot100】LeetCode—98. 验证二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

• 原题连接：98. 验证二叉搜索树

---

1- 思路

中序遍历（栈）+判断数组

• 1- 中序遍历
  • 借助队列 Stack 和 cur 指针实现
  • 1-1 Stack默认加入 root
  • 1-2 借助 while 实现遍历：
  • 1-3 如果 cur!=null 此时，继续左移
  • 1-4 否则，此时需要处理结果，将 cur.val 加到结果集，之后右移
• 2- 将中序的结果存入数组
  • 遍历数组判断是否有序

---

2- 实现

⭐98. 验证二叉搜索树——题解思路

class Solution {public boolean isValidBST(TreeNode root) {if(root==null){return true;}inorder(root);int[] nums = new int[res.size()];for(int i = 0 ; i < res.size() ; i++){nums[i] = res.get(i);}for(int i = 1 ; i < nums.length;i++){if(nums[i-1] >= nums[i]){return false;}}return true;}List<Integer> res = new ArrayList<>();public List<Integer> inorder(TreeNode root){// 栈+队列Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;if(root==null){return res;}while(cur!=null || !stack.isEmpty()){if(cur!=null){stack.push(cur);cur = cur.left;}else{cur = stack.pop();res.add(cur.val);cur = cur.right;}}return res;}}

---

3- ACM 实现

public class isValidBST {public static 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;}}public static TreeNode build(String str){if(str == null || str.length()==0){return null;}String input = str.replace("[","");input = input.replace("]","");String[] parts = input.split(",");Integer[] nums = new Integer[parts.length];for(int i = 0 ; i < parts.length;i++){if(!parts[i].equals("null")){nums[i] = Integer.parseInt(parts[i]);}else{nums[i] = null;}}Queue<TreeNode> queue = new LinkedList<>();TreeNode root = new TreeNode(nums[0]);queue.offer(root);int index = 1;while(!queue.isEmpty()&& index<parts.length){TreeNode node = queue.poll();if(index<nums.length && nums[index]!=null){node.left = new TreeNode(nums[index]);queue.offer(node.left);}index++;if(index<nums.length && nums[index]!=null){node.right = new TreeNode(nums[index]);queue.offer(node.right);}index++;}return root;}public static boolean isBST(TreeNode root){inorder(root);// 构造数组int[] nums = new int[res.size()];for(int i = 0 ; i < nums.length;i++){nums[i] = res.get(i);}for(int i = 1 ; i < nums.length;i++){if(nums[i-1] >= nums[i]){return false;}}return true;}static List<Integer> res = new ArrayList<>();public static List<Integer> inorder(TreeNode root){// 栈Stack<TreeNode> st = new Stack<>();TreeNode cur = root;while(cur!=null || !st.isEmpty()){if(cur!=null){st.add(cur);cur = cur.left;}else{cur = st.pop();res.add(cur.val);cur = cur .right;}}return res;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();TreeNode root = build(input);System.out.println("结果是"+isBST(root));}
}

这篇关于【Hot100】LeetCode—98. 验证二叉搜索树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---