最大二叉树
public TreeNode constructMaximumBinaryTree(int[] nums) {
return cons(nums, 0, nums.length);
}
private TreeNode cons(int[] nums, int begin, int end) {
if(begin >= end) {
return null;
}
int maxValue = nums[begin];
int maxIndex = begin;
for(int i = begin; i < end;i++) {
if(nums[i] > maxValue) {
maxValue = nums[i];
maxIndex = i;
}
}
TreeNode root = new TreeNode(maxValue);
root.left = cons(nums, begin, maxIndex);
root.right = cons(nums, maxIndex + 1, end);
return root;
}
合并二叉树
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1 == null) {
return root2;
}
if(root2 == null) {
return root1;
}
root1.val = root1.val + root2.val;
root1.left = mergeTrees(root1.left, root2.left);
root1.right = mergeTrees(root1.right,root2.right);
return root1;
}
二叉搜索树搜索
public TreeNode searchBST(TreeNode root, int val) {
if(root == null || root.val == val) {
return root;
}
if(root.val > val) {
return searchBST(root.left, val);
}
return searchBST(root.right, val);
}
验证二叉搜索树
private 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;
} else {
pre = root;
}
return isValidBST(root.right);
}
网友评论