class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE); 
    }
    public boolean isValidBST(TreeNode root,long left,long right){
        if(root == null) return true;
        if(root.val <= left || root.val >= right) return false;
        return isValidBST(root.left,left,root.val)&&isValidBST(root.right,root.val,right);
    }
}

class Solution {
    TreeNode pre = null;
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        if(!isValidBST(root.left)){
            return false;
        }
        if(pre != null && pre.val >= root.val){
            return false;
        }
        pre = root;
        return isValidBST(root.right);
    }
}

class Solution {
    int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        getMax(root);
        return res;
    }
    public int getMax(TreeNode root){
        if(root == null) return 0;
        int left = getMax(root.left);
        int right = getMax(root.right);
        int len = left+right;
        res = Math.max(len,res);
        return 1+Math.max(left,right);
    }
}

class Solution {
    public TreeNode convertBST(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        pre(root,list);
        int size = list.size();
        if(size == 0 || size == 1) return root;
        int curSum = 0;
        for(int i = size-1;i >= 0;i--){
            TreeNode node = list.get(i);
            curSum = node.val+curSum;
            node.val = curSum;
        }
        return root;
    }
    public void pre(TreeNode root,List<TreeNode> list){
        if(root == null) return;
        pre(root.left,list);
        list.add(root);
        pre(root.right,list);
    }
}

class Solution {
    int cur = 0;
    public TreeNode convertBST(TreeNode root) {
        if(root == null) return null;
        convertBST(root.right);
        cur = root.val+cur;
        root.val = cur;
        convertBST(root.left);
        return root;
    }
}