18th Day| 654.最大二叉树, 617.合并二叉树, 700.二叉搜索树中的搜索,98.验证二叉搜索树

LeetCode 654 最大二叉树

题目链接:654.最大二叉树

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {//左闭右开return traversal(nums, 0, nums.length);}public TreeNode traversal(int[] nums, int begin, int end){if(begin >= end){return null;}if(end - begin == 1){return new TreeNode(nums[begin]);}int maxValue = nums[begin];int index = begin;for(int i = begin+1; i < end; i++){if(nums[i] > maxValue){maxValue = nums[i];index = i;}}TreeNode node = new TreeNode(maxValue);node.left = traversal(nums, begin, index);node.right = traversal(nums, index+1, end);return node;}
}

LeetCode 617 合并二叉树

题目链接:617.合并二叉树

/** 直接操作原有的二叉树不需要创建新的 */
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1 == null) return root2;if(root2 == null) return root1;root1.val += root2.val;root1.left = mergeTrees(root1.left, root2.left);root1.right = mergeTrees(root1.right, root2.right);return root1; }
}

LeetCode 700 二叉搜索树中的搜索

题目链接:

/**递归 */
class Solution {public TreeNode searchBST(TreeNode root, int val) {if(root == null) return null;if(val < root.val) return searchBST(root.left, val);if(val > root.val) return searchBST(root.right, val);return root;}
}

LeetCode 98 验证二叉搜索树

题目链接:98.验证二叉搜索树

/**中序遍历 二叉搜索树就是一个升序数组 判断这个数组是不是有序的*/
class Solution {List<Integer> list = new ArrayList<>();public boolean isValidBST(TreeNode root) {boolean res = true;traversal(root);for(int i = 1; i < list.size(); i++){if(list.get(i) <= list.get(i-1)){res = false;break;}}return res;}public void traversal(TreeNode root){if(root == null) return;traversal(root.left);list.add(root.val);traversal(root.right);}
}
/**在递归的过程中直接判断是不是有序的,pre记录啦上一个节点 当前节点和上一个节点比较双指针优化*/
class Solution {TreeNode pre;public boolean isValidBST(TreeNode root) {if(root == null) return true;boolean left = isValidBST(root.left);if(pre != null && root.val <= pre.val){return false;}pre = root;boolean right = isValidBST(root.right);return left && right;}
}