三国类的网页游戏排行榜_网站建站网站域名申请_免费自制app软件_找培训机构的网站

654.最大二叉树

用中序遍历获取最终的二叉树节点 左闭右开

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return travelMax(nums, 0, nums.length);}public TreeNode travelMax(int nums[], int left, int right) {if(right - left < 1) return null;if(right - left == 1) return new TreeNode(nums[left]);int maxIndex = left;int maxValue = nums[maxIndex];for(int i = left; i < right; i++) {if(nums[i] > maxValue){maxValue = nums[i];maxIndex = i;}}TreeNode node = new TreeNode(maxValue);node.left = travelMax(nums, left, maxIndex);node.right = travelMax(nums, maxIndex + 1, right);return node;    }
}

在代码中，for 循环中不能将 right 替换成 nums.length，原因是递归函数 travelMax 的逻辑要求在每次递归时处理的是一个特定的子区间，而不是整个数组。下面具体分析：

1. right 是递归的边界

• 在递归中，travelMax(nums, left, right) 的逻辑是处理 nums 数组的 [left, right) 区间。
  • 这个区间是左闭右开，包含 left 但不包含 right。
  • 换句话说，right 是当前子区间的结束位置，不代表数组的结束。
• 如果在循环中写成 nums.length，就会忽略递归中传递的子区间范围。递归时，你希望遍历的是指定子区间 [left, right)，而不是整个数组。

---

2. 子区间范围的递归划分

• 每次递归，travelMax 会对数组进行划分为左右子区间：- 左子区间：[left, maxIndex)
  • 右子区间：[maxIndex + 1, right)
• 如果在 for 循环中强制使用 nums.length，就会忽略划分的逻辑，始终遍历整个数组，导致结果不正确。

---

3. 错误示例分析

如果写成：

for (int i = left; i < nums.length; i++) {if (nums[i] > maxValue) {maxValue = nums[i];maxIndex = i;}
}

问题是：

1. 初始的 travelMax(nums, 0, nums.length) 会遍历整个数组，这是正确的。
2. 但递归调用时，比如 travelMax(nums, 0, maxIndex)，你希望只遍历 [0, maxIndex)，但仍会遍历整个数组，导致逻辑混乱，可能访问不属于当前区间的元素。

---

4. 正确逻辑

在 for 循环中使用当前递归区间的边界 [left, right)，例如：

for (int i = left; i < right; i++) {if (nums[i] > maxValue) {maxValue = nums[i];maxIndex = i;}
}

• 这样可以确保 travelMax 函数只处理当前子区间的元素，且不会访问超出区间的部分。
• 每次递归都会通过 travelMax(nums, left, maxIndex) 和 travelMax(nums, maxIndex + 1, right) 进一步缩小范围，逐步构建树的左右子树。

---

总结

right 是当前递归处理的子区间的结束位置，其值可能小于 nums.length。将 right 写成 nums.length 会破坏递归逻辑，导致代码无法正确处理子区间，从而影响结果。

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

详细说明：

1. 判断空树：
   • 如果 root1 为空，说明 root1 没有树，那么合并结果直接返回 root2。
   • 如果 root2 为空，说明 root2 没有树，那么合并结果直接返回 root1。
2. 合并节点值：
   • 如果两个节点都不为空，就将 root1 的值与 root2 的值相加，即 root1.val += root2.val，表示合并这两个节点。
3. 递归合并左子树和右子树：
   • 递归地合并 root1 的左子树和 root2 的左子树，root1.left = mergeTrees(root1.left, root2.left)。
   • 同理，递归地合并右子树 root1.right = mergeTrees(root1.right, root2.right)。
4. 返回合并后的树：
   • 最后，返回更新后的 root1，这棵树就是合并后的结果。

700.二叉搜索树中的搜索

因为二叉搜索树的特性 导致迭代法也很简单

错误的迭代写法

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

问题：

if 和 else 之间没有 else if 或明确的分支条件。这样，在某些情况下，val == root.val 也会被进入到 root = root.right 的分支（因为没有 else if），导致错误地更新了 root，即使找到了目标节点。

解决方法：

将 if(val > root.val) 和 else 用 else if 连接，确保只有在 val < root.val 时，才向左子树移动，只有在 val > root.val 时，才向右子树移动，else 才表示找到了目标节点。

正确代码

class Solution {public TreeNode searchBST(TreeNode root, int val) {while (root != null) {if (val < root.val) {root = root.left;} else if (val > root.val) {root = root.right;} else {return root; // 找到了值等于 val 的节点}}return null; // 没有找到目标值，返回 null 必须写}
}

迭代法 要新建树 空间复杂度较高

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

验证二叉搜索树

递归法

class Solution {// 递归TreeNode max;public boolean isValidBST(TreeNode root) {if (root == null) {return true;}// 左boolean left = isValidBST(root.left);if (!left) {return false;}// 中if (max != null && root.val <= max.val) {return false;}max = root;// 右boolean right = isValidBST(root.right);return right;}
}

关键点：

• 中序遍历的顺序：在 BST 中，中序遍历的结果应该是严格递增的序列。- 检查过程中通过比较当前节点值和 max 的值来判断是否满足递增性。