/*** Definition for a binary tree node.* public 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;* }* }*/
class Solution {private int ans;public int diameterOfBinaryTree(TreeNode root) {dfs(root);return ans;}private int dfs(TreeNode node){if(node == null)return -1;//如果空的话返回-1 后面+1可以补成0int lLen = dfs(node.left) + 1;//左子树最大链长+1int rLen = dfs(node.right) + 1;//右字数最大链长+1ans = Math.max(ans,lLen + rLen);//两条链拼成路径return Math.max(lLen,rLen);//当前字数的最大链长}
}
/*** Definition for a binary tree node.* public 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;* }* }*/
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();List<List<Integer>> res = new ArrayList<>();if(root != null)queue.add(root);while(!queue.isEmpty()){List<Integer> temp = new ArrayList<>();for(int i = queue.size();i>0;i--){TreeNode node = queue.poll();//返回并弹出temp.add(node.val);if(node.left != null)queue.add(node.left);if(node.right != null)queue.add(node.right);}res.add(temp);}return res;}
} 
/*** Definition for a binary tree node.* public 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;* }* }*/
class Solution {public boolean isValidBST(TreeNode root) {return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);}//区间private boolean isValidBST(TreeNode node,long left,long right){if(node == null)return true;long x = node.val;return left<x && x<right &&isValidBST(node.left,left,x)&&isValidBST(node.right,x,right);}
}
/*** Definition for a binary tree node.* public 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;* }* }*/
class Solution {private long pre = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root == null)return true;//递归终止的条件if(!isValidBST(root.left) || root.val <= pre)return false;//遍历完左子树看端点值 pre = root.val;//更新端点值return isValidBST(root.right);//去右节点找左子树继续看}
}
/*** Definition for a binary tree node.* public 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;* }* }*/
class Solution {public boolean isValidBST(TreeNode root) {return dfs(root)[1] != Long.MAX_VALUE;}private long[] dfs(TreeNode node) {//大于左边的最大值 小于右边的最小值if (node == null) {return new long[]{Long.MAX_VALUE, Long.MIN_VALUE};}//最大值 最小值long[] left = dfs(node.left);long[] right = dfs(node.right);long x = node.val;// 也可以在递归完左子树之后立刻判断，如果发现不是二叉搜索树，就不用递归右子树了if (x <= left[1] || x >= right[0]) {return new long[]{Long.MIN_VALUE, Long.MAX_VALUE};}//不成立return new long[]{Math.min(left[0], x), Math.max(right[1], x)};}
}
/*** Definition for a binary tree node.* public 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;* }* }*/
class Solution {//二叉搜索树 左<中<右 故中序遍历是递增的int res , k;void dfs(TreeNode root){if(root == null)return ;dfs(root.left);if(k==0)return ;if(--k == 0)res = root.val;dfs(root.right);}public int kthSmallest(TreeNode root, int k) {this.k = k;dfs(root);return res;}
}
