算法训练营（day20）
654.最大二叉树
题目链接：https://leetcode.cn/problems/maximum-binary-tree/description/
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
- 创建一个根节点，其值为
nums 中的最大值。
- 递归地在最大值 左边 的 子数组前缀上 构建左子树。
- 递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 *最大二叉树* 。
解题思路
解题过程：递归
- 创建一个根节点，其值为
nums 中的最大值。
- 递归地在最大值 左边 的 子数组前缀上 构建左子树。
- 递归地在最大值 右边 的 子数组后缀上 构建右子树。
- 返回
nums 构建的 最大二叉树 。
详细代码
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
|
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return buildTree(nums, 0, nums.length);
}
public TreeNode buildTree(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 maxValue = nums[leftIndex];
for(int i = leftIndex + 1; i < rightIndex; i++){
if(nums[i] > maxValue){
maxIndex = i;
maxValue = nums[i];
}
}
TreeNode root = new TreeNode(maxValue);
root.left = buildTree(nums, leftIndex, maxIndex);
root.right = buildTree(nums, maxIndex + 1, rightIndex);
return root;
}
}
|
617.合并二叉树
题目链接：https://leetcode.cn/problems/merge-two-binary-trees/description/
给你两棵二叉树： root1 和 root2 。想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
解题思路
解题过程：
取 root1 作为主二叉树（记作a），root2作为合并树（记作b）
- 当 a 和 b 都有该节点的值，则 a + b
- a 有， b 没有节点值，则保留 a
- a 没有， b有节点值，则在a中添加 b 节点值
返回 root1
详细代码
解法一：递归
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 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
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
44
45
46
47
48
49
50
51
52
|
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1 == null){
return root2;
}
if(root2 == null){
return root1;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root1);
stack.push(root2);
while(!stack.isEmpty()){
TreeNode node2 = stack.pop();
TreeNode node1 = stack.pop();
node1.val += node2.val;
if(node1.right != null && node2.right != null){
stack.push(node1.right);
stack.push(node2.right);
}else{
if(node1.right == null){
node1.right = node2.right;
}
}
if(node1.left != null && node2.left != null){
stack.push(node1.left);
stack.push(node2.left);
}else{
if(node1.left == null){
node1.left = node2.left;
}
}
}
return root1;
}
}
|
700.二叉搜索树中的搜索
题目链接：https://leetcode.cn/problems/search-in-a-binary-search-tree/description/
给定二叉搜索树（BST）的根节点 root 和一个整数值 val。你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
解题思路
解题过程：
二叉搜索树满足 左小右大 的节点特性
判断 val 和当前节点值的大小关系
val = root.val，返回以这个节点为根节点的子树val > root.val，则递归 右子树val < root.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) {
if(root == null || root.val == val){
return root;
}
if(val < root.val){
return searchBST(root.left, val);
}
if(val > root.val){
return searchBST(root.right, val);
}
return 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
28
29
|
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
while(root != null){
if(root.val > val){
root = root.left;
}else if(root.val < val){
root = root.right;
}else{
return root;
}
}
return null;
}
}
|
98.验证二叉搜索树
题目链接：https://leetcode.cn/problems/validate-binary-search-tree/description/
给你一个二叉树的根节点 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
28
29
30
31
32
33
|
class Solution {
TreeNode max;
public boolean isValidBST(TreeNode root) {
if(root == null){
return true;
}
if(!isValidBST(root.left)){
return false;
}
if(max != null && root.val <= max.val){
return false;
}
max = root;
return isValidBST(root.right);
}
}
|
解法二：迭代
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
|
class Solution {
public boolean isValidBST(TreeNode root) {
if(root == null){
return true;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
while(root != null || !stack.isEmpty()){
while(root != null){
stack.push(root);
root = root.left;
}
TreeNode mid = stack.pop();
if(pre != null && mid.val <= pre.val){
return false;
}
pre = mid;
root = mid.right;
}
return true;
}
}
|
