代码随想录算法训练营Day15

654.最大二叉树

力扣题目链接：. - 力扣（LeetCode）

前序递归、循环不变量

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return findmax(nums,0,nums.length);}public TreeNode findmax(int[] nums,int leftindex,int rightindex){if(rightindex==leftindex){return null;}if(rightindex-leftindex==1){return new TreeNode(nums[leftindex]);}int max=nums[leftindex];int maxindex=leftindex;for(int i=leftindex;i<rightindex;i++){if(nums[i]>max){max=nums[i];maxindex=i;}}TreeNode root=new TreeNode(max);root.left=findmax(nums,leftindex,maxindex);root.right=findmax(nums,maxindex+1,rightindex);return root;}
}

617.合并二叉树

力扣题目链接：. - 力扣（LeetCode）​​​​​​

前序递归

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

700.二叉搜索树中的搜索

力扣题目链接：. - 力扣（LeetCode）

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

98.验证二叉搜索树

力扣题目链接：. - 力扣（LeetCode）

中序递归

class Solution {public boolean isValidBST(TreeNode root) {List<Integer> res=new ArrayList<>();midorder(root,res);for(int i=0;i<res.size()-1;i++){if(res.get(i)>=res.get(i+1)){return false;}}return true;}public void midorder(TreeNode root,List<Integer> res){if(root==null){return;}midorder(root.left,res);res.add(root.val);midorder(root.right,res);}
}