LeetCode 654.最大二叉树
分析1.0
- if（start == end） return节点索引
locateMaxNode（arr，start，end）
new root = 最大索引对应节点
max.right = 最大节点右侧子数组的最大值 要保证能够递归
max.left = 最大节点左侧子数组的最大值
class Solution {
int cnt = 1;
public TreeNode constructMaximumBinaryTree(int[] nums) {
return locate(nums, 0, nums.length-1);
}
public TreeNode locate(int[] nums, int start, int end){
System.out.println("start---"+start+"---end---"+end);
// 只剩一个节点了
if(end == start){
return new TreeNode(nums[start]);
}
int maxNumIndex = getMaxValIndex(nums,start,end);
TreeNode root = new TreeNode(nums[maxNumIndex]);
if(maxNumIndex > start){
System.out.println("左边");
root.left = locate(nums, start, maxNumIndex-1);
}
// if(maxNumIndex < nums.length-1) 错的
if(maxNumIndex < end){
System.out.println("右边");
root.right = locate(nums, maxNumIndex+1, end);
}
return root;
}
public int getMaxValIndex(int[] nums, int start, int end){
int num = -1, index = -1;
for(int i = start; i <= end; i++){
if(num < nums[i]){
num = nums[i];
index = i;
}
}
System.out.println("第"+ cnt++ +"次最大值为------" + nums[index]);
return index;
}
}失误
递归的边界不是 0 和 nums.length-1 每次递归索引都会发生变化
LeetCode 617.合并二叉树
分析1.0
- if（root1空 或 root2空，return 不空的那个节点
root1 += root2
preOrder(root1，root2）
失误
return判断不必搞四种，root1空 return root2 root2空return root1就行
分析2.0
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
return merge(root1, root2);
}
public TreeNode merge(TreeNode root1, TreeNode root2){
if(root1 == null && root2 != null){
return root2;
}
if(root1 != null && root2 == null){
return root1;
}
if(root1 == null && root2 == null){
return null;
}
System.out.println(root1.val +" "+ root2.val);
root1.val += root2.val;
root1.left = merge(root1.left, root2.left);
root1.right = merge(root1.right, root2.right);
return root1;
}
}LeetCode 700.二叉搜索树中的搜索
分析1.0
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if(root == null){
return null;
}else if(root.val == val){
return root;
}else if(root.val < val){
return searchBST(root.right, val);
}else{
return searchBST(root.left, val);
}
}
}LeetCode 验证二叉搜索树
分析1.0
找到树根节点，遍历左子树看是不是都小于它，再遍历右子树，看是不是大于它，先根遍历
失误
想着用两次深度递归解决问题 没想好
分析2.0
class Solution {
ArrayList<Integer> list = new ArrayList();
public boolean isValidBST(TreeNode root) {
inOrder(root);
for(int i = 0; i < list.size()-1; i++){
if(list.get(i) >= list.get(i+1)){
return false;
}
}
return true;
}
public void inOrder(TreeNode root){
if(root == null){
return;
}
inOrder(root.left);
list.add(root.val);
inOrder(root.right);
}
}二叉搜索树中序遍历形成的序列是严格升序序列！！！
总结
- 递归的边界不是 0 和 nums.length-1 每次递归，递归函数边界索引都会发生变化
解题注意数据集特点，元素大小、范围、正负等，以及要求的时间空间复杂度
二叉搜索树中序遍历形成的序列是升序序列！！！
常用变量名增量更新
size、val、ans、cnt、cur、pre、next、left、right、index、gap、tar、res、src、len、start、end、flag、ch
