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;
    }