首页 > 代码库 > leecode 树是否是平衡树 java

leecode 树是否是平衡树 java

2024-07-10 07:19:19   219人阅读

https://oj.leetcode.com/problems/validate-binary-search-tree/

1.中序遍历是否有序

/** * Definition for binary tree * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    private int a=-(1<<31);      public boolean isValidBST(TreeNode root) {                      return middle(root);                   }    public boolean middle(TreeNode root)    {        if(root==null) return true;        if(!middle(root.left)) return false;        if(root.val<=a)         {            return false;                }                a=root.val;        return middle(root.right);                    }}

　　2.记住每个节点的范围 开始时候（min,max）设为int最大，最小，然后在左子树上范围为（min, root.val） 判断节点是否在范围；

 

 

/** * Definition for binary tree * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */public class Solution {    public boolean isValidBST(TreeNode root) {                        int min=-(1<<31);        int max=1<<31-1;       return isValid(root,min,max);                    }    public boolean isValid(TreeNode root,int min,int max)    {        if(root==null) return true;        if(root.val>min&&root.val<max)        {            return isValid(root.left,min,root.val)&&isValid(root.right,root.val,max);                    }        return false;                    }}

　　

 


联系
我们