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 conta ...
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 }
原标题:98. Validate Binary Search Tree
关键词:
*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们:
admin#shaoqun.com
(#换成@)。