Week 23 @ 2025 算法周记【二叉树 + nSum】
- 1 二叉树
- 2 nSum
- 2.1 LC 15. 3Sum 三数之和
- 2.2 LC 18. 4Sum 四数之和
二叉树
LC 654. Maximum Binary Tree 最大二叉树
https://leetcode.com/problems/maximum-binary-tree/description/
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func constructMaximumBinaryTree(nums []int) *TreeNode {
if len(nums) == 0 {
return nil
}
i := findMaxIndex(nums)
root := &TreeNode{Val: nums[i]}
root.Left = constructMaximumBinaryTree(nums[:i])
root.Right = constructMaximumBinaryTree(nums[i+1:])
return root
}
func findMaxIndex(nums []int) int {
maxIndex := 0
v := nums[0]
for i := 1; i < len(nums); i++ {
if nums[i] > v {
maxIndex = i
v = nums[i]
}
}
return maxIndex
}LC 105. Construct Binary Tree from Preorder and Inorder Traversal 从前序与中序遍历序列构造二叉树
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder) == 0 {
return nil
}
if len(preorder) == 1 {
return &TreeNode{Val: preorder[0]}
}
rootVal := preorder[0]
idx := slices.Index(inorder, rootVal)
root := &TreeNode{Val: rootVal}
root.Left = buildTree(
preorder[1:1+idx],
inorder[:idx],
)
root.Right = buildTree(
preorder[idx+1:],
inorder[idx+1:],
)
return root
}LC 106. Construct Binary Tree from Inorder and Postorder Traversal 从中序与后序遍历序列构造二叉树
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(inorder []int, postorder []int) *TreeNode {
if len(postorder) == 0 {
return nil
}
if len(postorder) == 1 {
return &TreeNode{Val: postorder[len(postorder)-1]}
}
rootVal := postorder[len(postorder)-1]
root := &TreeNode{Val: rootVal}
idx := slices.Index(inorder, rootVal)
root.Left = buildTree(
inorder[:idx],
postorder[:idx],
)
root.Right = buildTree(
inorder[idx+1:],
postorder[idx:len(postorder)-1],
)
return root
}LC 889. Construct Binary Tree from Preorder and Postorder Traversal 根据前序和后序遍历构造二叉树
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
if len(preorder) == 0 {
return nil
}
if len(preorder) == 1 {
return &TreeNode{Val: preorder[0]}
}
rootVal := preorder[0]
root := &TreeNode{Val: rootVal}
nextRootVal := preorder[1]
leftSize := slices.Index(postorder, nextRootVal) + 1
root.Left = constructFromPrePost(
preorder[1:1+leftSize],
postorder[:leftSize],
)
root.Right = constructFromPrePost(
preorder[1+leftSize:],
postorder[leftSize:len(postorder)-1],
)
return root
}nSum
LC 15. 3Sum 三数之和
https://leetcode.com/problems/3sum/description/
func threeSum(nums []int) [][]int {
sort.Ints(nums)
result := [][]int{}
for i, v := range nums {
if i > 0 && nums[i-1] == v {
continue
}
pairs := twoSumTarget(nums[i+1:], -v)
for _, pair := range pairs {
result = append(result, []int{v, pair[0], pair[1]})
}
}
return result
}
func twoSumTarget(nums []int, target int) (pairs [][]int) {
i, j := 0, len(nums) - 1
for i < j {
sum := nums[i] + nums[j]
if sum == target {
pairs = append(pairs, []int{nums[i], nums[j]})
for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
} else if sum < target {
for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
} else {
for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
}
}
return
}LC 18. 4Sum 四数之和
https://leetcode.com/problems/4sum/description/
func fourSum(nums []int, target int) [][]int {
sort.Ints(nums)
result := [][]int{}
for i, v := range nums {
if i > 0 && nums[i-1] == v {
continue
}
pairs := threeSumTarget(nums[i+1:], target-v)
for _, pair := range pairs {
result = append(result, []int{v, pair[0], pair[1], pair[2]})
}
}
return result
}
func threeSumTarget(nums []int, target int) [][]int {
result := [][]int{}
for i, v := range nums {
if i > 0 && nums[i-1] == v {
continue
}
pairs := twoSumTarget(nums[i+1:], target-v)
for _, pair := range pairs {
result = append(result, []int{v, pair[0], pair[1]})
}
}
return result
}
func twoSumTarget(nums []int, target int) (pairs [][]int) {
i, j := 0, len(nums) - 1
for i < j {
sum := nums[i] + nums[j]
if sum == target {
pairs = append(pairs, []int{nums[i], nums[j]})
for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
} else if sum < target {
for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
} else {
for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
}
}
return
}不用 3Sum
（本质上就是把 3Sum 写到一起了。。）
func fourSum(nums []int, target int) [][]int {
sort.Ints(nums)
result := [][]int{}
for i := 0; i < len(nums); i++ {
if i > 0 && nums[i] == nums[i-1] { continue }
for j := i+1; j < len(nums); j++ {
if j > i+1 && nums[j] == nums[j-1] { continue }
pairs := twoSumTarget(nums[j+1:], target-nums[i]-nums[j])
for _, pair := range pairs {
result = append(result, []int{nums[i], nums[j], pair[0], pair[1]})
}
}
}
return result
}
func twoSumTarget(nums []int, target int) (pairs [][]int) {
i, j := 0, len(nums) - 1
for i < j {
sum := nums[i] + nums[j]
if sum == target {
pairs = append(pairs, []int{nums[i], nums[j]})
for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
} else if sum < target {
for v := nums[i]; i < len(nums) && nums[i] == v; i++ {}
} else {
for v := nums[j]; j >= 0 && nums[j] == v; j-- {}
}
}
return
}
, multiple selections available,