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));}
}
