验证二叉搜索树
解法一
递归
每次判断cur是否在left与right之间
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); } }
二叉树的直径
解法一
递归
与求二叉树深度类似
getMax返回的是左右子树的最大深度
所有边就等于left-1+right-1+2 = left+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; } }
