DAY17-二叉树

LeetCode654.最大二叉树

    public TreeNode constructMaximumBinaryTree(int[] nums) {return maxTree(nums,0,nums.length);}public TreeNode maxTree(int[]nums,int start,int end) {//递归结束if(start==end) {return null;}//如果只有一个值的话，直接构建节点if(end-start==1) {return new TreeNode(nums[start]);}//如果数组里有多个值则需要找到最大值并进行切割int max=nums[start],index=start;for(int i=start;i<end;i++) {if(nums[i]>max) {max=nums[i];index=i;}}//创建根节点TreeNode root = new TreeNode(max);//进入左右节点递归root.left=maxTree(nums,start,index);root.right=maxTree(nums,index+1,end);//返回根节点return root;}

LeetCode617.合并二叉树

    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {//递归结束条件if(root1==null) return root2;if(root2==null) return root1;//创建根节点进行左右递归TreeNode root = new TreeNode(root1.val+root2.val);root.left=mergeTrees(root1.left,root2.left);root.right=mergeTrees(root1.right,root2.right);return root;}

LeetCode700.二叉搜索树中的搜索

    public TreeNode searchBST(TreeNode root, int val) {if(root==null) return null;while(root!=null) {if(root.val==val) return root;else if(root.val>val) {root=root.left;}else if(root.val<val) {root=root.right;}}return null;}

LeetCode98.验证二叉搜索树

	public List<Integer> list = new ArrayList<>();public boolean isValidBST(TreeNode root) {if(root==null) return true;boolean left = isValidBST(root.left);list.add(root.val);if(list.size()>1) {if(list.get(list.size()-2)>=root.val) {return false;}}boolean right = isValidBST(root.right);return left && right;}