最大二叉树
link：654. 最大二叉树 - 力扣（LeetCode）
思路分析
在数组中遍历找到最大值（根节点），分割得到左右子树，再回溯遍历左右子树（还是先找到最大值作为子树的根节点再遍历）
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return constructMaximumBinaryTree1(nums,0,nums.length);
}
public TreeNode constructMaximumBinaryTree1(int[] nums,int leftIndex, int rightIndex) {
if(rightIndex - leftIndex == 0) {
return null;
}
if(rightIndex - leftIndex == 1) {
return new TreeNode(nums[leftIndex]);
}
int maxIndex = leftIndex;
int maxVal = nums[leftIndex];
for(int i = leftIndex; i < rightIndex; i++) {
if(nums[i] > maxVal) {
maxVal = nums[i];
maxIndex = i;
}
}
TreeNode root = new TreeNode(maxVal);
root.left = constructMaximumBinaryTree1(nums,leftIndex,maxIndex);
root.right = constructMaximumBinaryTree1(nums,maxIndex + 1,rightIndex);
return root;
}
}
|
Tips
左闭右开区间的优点
1.简化边界处理：使用左闭右开区间 [leftIndex, rightIndex) 意味着 rightIndex 是不包含的结束边界.
2.递归的分区更直观：分区时可以直接用 leftIndex 到 maxIndex 和 maxIndex + 1 到 rightIndex，无需额外调整索引。
1
2
| root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);
root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);
|
3.避免边界错误：半开区间让右边界始终指向范围的下一个位置，避免了因“是否包含结束位置”而导致的边界错误，尤其在处理数组下标时可以减少出错的风险.
合并二叉树
link：617. 合并二叉树 - 力扣（LeetCode）
思路分析
虽然题目说了合并过程必须从根节点开始，但是我们给定的数据内容已经满足条件（hh 冤大头 还想着要先判断一下大小）
直接无脑加就是了，主要就是判空递归.
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
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;
}
}
|
二叉搜索树中的搜索
link：700. 二叉搜索树中的搜索 - 力扣（LeetCode）
思路分析
因为给的是二叉搜索树，最邻近的左子树根节点比root小，最邻近的右子树根节点比root大，所以用val和跟root比较，再遍历递归对应的子树即可.（相当于左右划分）
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if(root == null || root.val == val) {
return root;
}
if(val < root.val) {
return searchBST(root.left, val);
}else {
return searchBST(root.right, val);
}
}
}
|
迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
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;
}
}
return null;
}
}
|
