你的位置:首页 > Java教程

[Java教程]98. Validate Binary Search Tree


Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.

思路:中序排列为排序好的数组(数组元素一次增大);数组中不能有重复元素。

代码如下:

 1 /** 2  * Definition for a binary tree node. 3  * public class TreeNode { 4  *   int val; 5  *   TreeNode left; 6  *   TreeNode right; 7  *   TreeNode(int x) { val = x; } 8  * } 9 */10 public class Solution {11   public boolean isValidBST(TreeNode root) {12    13     if(root==null||(root.left==null&&root.right==null))14     return true;15     ArrayList<Integer> list=ParentAndSon(root);16      int[] nums=new int[list.size()];17      int[] nums1=new int[list.size()];18      for(int i=0;i<list.size();i++)19      {20        nums[i]=list.get(i);21        nums1[i]=list.get(i);22      }23      Arrays.sort(nums);24   25      if(nums[0]!=nums1[0])26      return false;27      for(int i=1;i<nums.length;i++)28      {29      if(nums1[i]!=nums[i]||nums[i]==nums[i-1])30      return false;31      32      }33   return true;34   }35   public ArrayList<Integer> ParentAndSon(TreeNode root){36     ArrayList<Integer> list=new ArrayList<>();37     if(root.left!=null)38     list.addAll(ParentAndSon(root.left));39     40     list.add(root.val);41     42     if(root.right!=null)43     list.addAll(ParentAndSon(root.right));44     return list;45   }46 }