Skip to content

Commit 3c1ad91

Browse files
halfrosthalfrost
committed
Add solution 0538、1038
1 parent 3bd8dd1 commit 3c1ad91

32 files changed

+1328
-661
lines changed

‎README.md

Lines changed: 478 additions & 478 deletions
Large diffs are not rendered by default.

‎leetcode/0538.Convert-BST-to-Greater-Tree/538. Convert BST to Greater Tree.go

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package leetcode
2+
3+
import (
4+
"github.com/halfrost/LeetCode-Go/structures"
5+
)
6+
7+
// TreeNode define
8+
type TreeNode = structures.TreeNode
9+
10+
/**
11+
* Definition for a binary tree node.
12+
* type TreeNode struct {
13+
* Val int
14+
* Left *TreeNode
15+
* Right *TreeNode
16+
* }
17+
*/
18+
19+
func convertBST(root *TreeNode) *TreeNode {
20+
if root == nil {
21+
return root
22+
}
23+
sum := 0
24+
dfs538(root, &sum)
25+
return root
26+
}
27+
28+
func dfs538(root *TreeNode, sum *int) {
29+
if root == nil {
30+
return
31+
}
32+
dfs538(root.Right, sum)
33+
root.Val += *sum
34+
*sum = root.Val
35+
dfs538(root.Left, sum)
36+
}

‎leetcode/0538.Convert-BST-to-Greater-Tree/538. Convert BST to Greater Tree_test.go

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
7+
"github.com/halfrost/LeetCode-Go/structures"
8+
)
9+
10+
type question538 struct {
11+
para538
12+
ans538
13+
}
14+
15+
// para 是参数
16+
// one 代表第一个参数
17+
type para538 struct {
18+
one []int
19+
}
20+
21+
// ans 是答案
22+
// one 代表第一个答案
23+
type ans538 struct {
24+
one []int
25+
}
26+
27+
func Test_Problem538(t *testing.T) {
28+
29+
qs := []question538{
30+
31+
{
32+
para538{[]int{3, 1, structures.NULL, 0, structures.NULL, -4, structures.NULL, structures.NULL, -2}},
33+
ans538{[]int{3, 4, structures.NULL, 4, structures.NULL, -2, structures.NULL, structures.NULL, 2}},
34+
},
35+
36+
{
37+
para538{[]int{2, 1}},
38+
ans538{[]int{2, 3}},
39+
},
40+
41+
{
42+
para538{[]int{}},
43+
ans538{[]int{}},
44+
},
45+
46+
{
47+
para538{[]int{4, 1, 6, 0, 2, 5, 7, structures.NULL, structures.NULL, structures.NULL, 3, structures.NULL, structures.NULL, structures.NULL, 8}},
48+
ans538{[]int{30, 36, 21, 36, 35, 26, 15, structures.NULL, structures.NULL, structures.NULL, 33, structures.NULL, structures.NULL, structures.NULL, 8}},
49+
},
50+
51+
{
52+
para538{[]int{0, structures.NULL, 1}},
53+
ans538{[]int{1, structures.NULL, 1}},
54+
},
55+
56+
{
57+
para538{[]int{1, 0, 2}},
58+
ans538{[]int{3, 3, 2}},
59+
},
60+
61+
{
62+
para538{[]int{3, 2, 4, 1}},
63+
ans538{[]int{7, 9, 4, 10}},
64+
},
65+
}
66+
67+
fmt.Printf("------------------------Leetcode Problem 538------------------------\n")
68+
69+
for _, q := range qs {
70+
_, p := q.ans538, q.para538
71+
fmt.Printf("【input】:%v ", p)
72+
root := structures.Ints2TreeNode(p.one)
73+
fmt.Printf("【output】:%v \n", structures.Tree2ints(convertBST(root)))
74+
}
75+
fmt.Printf("\n\n\n")
76+
}

‎leetcode/0538.Convert-BST-to-Greater-Tree/README.md

Lines changed: 106 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,106 @@
1+
# [538. Convert BST to Greater Tree](https://leetcode.com/problems/convert-bst-to-greater-tree/)
2+
3+
## 题目
4+
5+
Given the `root` of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.
6+
7+
As a reminder, a *binary search tree* is a tree that satisfies these constraints:
8+
9+
- The left subtree of a node contains only nodes with keys **less than** the node's key.
10+
- The right subtree of a node contains only nodes with keys **greater than** the node's key.
11+
- Both the left and right subtrees must also be binary search trees.
12+
13+
**Note:** This question is the same as 1038: [https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/](https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/)
14+
15+
**Example 1:**
16+
17+
![https://assets.leetcode.com/uploads/2019/05/02/tree.png](https://assets.leetcode.com/uploads/2019/05/02/tree.png)
18+
19+
```
20+
Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
21+
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
22+
```
23+
24+
**Example 2:**
25+
26+
```
27+
Input: root = [0,null,1]
28+
Output: [1,null,1]
29+
```
30+
31+
**Example 3:**
32+
33+
```
34+
Input: root = [1,0,2]
35+
Output: [3,3,2]
36+
```
37+
38+
**Example 4:**
39+
40+
```
41+
Input: root = [3,2,4,1]
42+
Output: [7,9,4,10]
43+
```
44+
45+
**Constraints:**
46+
47+
- The number of nodes in the tree is in the range `[0, 104]`.
48+
- `104 <= Node.val <= 104`
49+
- All the values in the tree are **unique**.
50+
- `root` is guaranteed to be a valid binary search tree.
51+
52+
## 题目大意
53+
54+
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
55+
56+
提醒一下，二叉搜索树满足下列约束条件：
57+
58+
- 节点的左子树仅包含键 小于 节点键的节点。
59+
- 节点的右子树仅包含键 大于 节点键的节点。
60+
- 左右子树也必须是二叉搜索树。
61+
62+
## 解题思路
63+
64+
- 根据二叉搜索树的有序性，想要将其转换为累加树，只需按照 右节点 - 根节点 - 左节点的顺序遍历，并累加和即可。
65+
- 此题同第 1038 题。
66+
67+
## 代码
68+
69+
```go
70+
package leetcode
71+
72+
import (
73+
"github.com/halfrost/LeetCode-Go/structures"
74+
)
75+
76+
// TreeNode define
77+
type TreeNode = structures.TreeNode
78+
79+
/**
80+
* Definition for a binary tree node.
81+
* type TreeNode struct {
82+
* Val int
83+
* Left *TreeNode
84+
* Right *TreeNode
85+
* }
86+
*/
87+
88+
func convertBST(root *TreeNode) *TreeNode {
89+
if root == nil {
90+
return root
91+
}
92+
sum := 0
93+
dfs538(root, &sum)
94+
return root
95+
}
96+
97+
func dfs538(root *TreeNode, sum *int) {
98+
if root == nil {
99+
return
100+
}
101+
dfs538(root.Right, sum)
102+
root.Val += *sum
103+
*sum = root.Val
104+
dfs538(root.Left, sum)
105+
}
106+
```

‎leetcode/1038.Binary-Search-Tree-to-Greater-Sum-Tree/1038. Binary Search Tree to Greater Sum Tree.go

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package leetcode
2+
3+
import (
4+
"github.com/halfrost/LeetCode-Go/structures"
5+
)
6+
7+
// TreeNode define
8+
type TreeNode = structures.TreeNode
9+
10+
/**
11+
* Definition for a binary tree node.
12+
* type TreeNode struct {
13+
* Val int
14+
* Left *TreeNode
15+
* Right *TreeNode
16+
* }
17+
*/
18+
19+
func bstToGst(root *TreeNode) *TreeNode {
20+
if root == nil {
21+
return root
22+
}
23+
sum := 0
24+
dfs1038(root, &sum)
25+
return root
26+
}
27+
28+
func dfs1038(root *TreeNode, sum *int) {
29+
if root == nil {
30+
return
31+
}
32+
dfs1038(root.Right, sum)
33+
root.Val += *sum
34+
*sum = root.Val
35+
dfs1038(root.Left, sum)
36+
}

‎leetcode/1038.Binary-Search-Tree-to-Greater-Sum-Tree/1038. Binary Search Tree to Greater Sum Tree_test.go

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
7+
"github.com/halfrost/LeetCode-Go/structures"
8+
)
9+
10+
type question1038 struct {
11+
para1038
12+
ans1038
13+
}
14+
15+
// para 是参数
16+
// one 代表第一个参数
17+
type para1038 struct {
18+
one []int
19+
}
20+
21+
// ans 是答案
22+
// one 代表第一个答案
23+
type ans1038 struct {
24+
one []int
25+
}
26+
27+
func Test_Problem1038(t *testing.T) {
28+
29+
qs := []question1038{
30+
31+
{
32+
para1038{[]int{3, 1, structures.NULL, 0, structures.NULL, -4, structures.NULL, structures.NULL, -2}},
33+
ans1038{[]int{3, 4, structures.NULL, 4, structures.NULL, -2, structures.NULL, structures.NULL, 2}},
34+
},
35+
36+
{
37+
para1038{[]int{2, 1}},
38+
ans1038{[]int{2, 3}},
39+
},
40+
41+
{
42+
para1038{[]int{}},
43+
ans1038{[]int{}},
44+
},
45+
46+
{
47+
para1038{[]int{4, 1, 6, 0, 2, 5, 7, structures.NULL, structures.NULL, structures.NULL, 3, structures.NULL, structures.NULL, structures.NULL, 8}},
48+
ans1038{[]int{30, 36, 21, 36, 35, 26, 15, structures.NULL, structures.NULL, structures.NULL, 33, structures.NULL, structures.NULL, structures.NULL, 8}},
49+
},
50+
51+
{
52+
para1038{[]int{0, structures.NULL, 1}},
53+
ans1038{[]int{1, structures.NULL, 1}},
54+
},
55+
56+
{
57+
para1038{[]int{1, 0, 2}},
58+
ans1038{[]int{3, 3, 2}},
59+
},
60+
61+
{
62+
para1038{[]int{3, 2, 4, 1}},
63+
ans1038{[]int{7, 9, 4, 10}},
64+
},
65+
}
66+
67+
fmt.Printf("------------------------Leetcode Problem 1038------------------------\n")
68+
69+
for _, q := range qs {
70+
_, p := q.ans1038, q.para1038
71+
fmt.Printf("【input】:%v ", p)
72+
root := structures.Ints2TreeNode(p.one)
73+
fmt.Printf("【output】:%v \n", structures.Tree2ints(bstToGst(root)))
74+
}
75+
fmt.Printf("\n\n\n")
76+
}

0 commit comments

Comments
 (0)