Week 27 @ 2025 算法周记【二叉树 + 二叉搜索树】
二叉树
LC 652. Find Duplicate Subtrees 寻找重复的子树
https://leetcode.com/problems/find-duplicate-subtrees/
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findDuplicateSubtrees(root *TreeNode) (result []*TreeNode) {
m := make(map[string]int)
dfs(root, m, &result)
return result
}
func dfs(root *TreeNode, m map[string]int, result *[]*TreeNode) string {
if root == nil {
return ""
}
left := dfs(root.Left, m, result)
right := dfs(root.Right, m, result)
subtree := left + "," + right + "," + strconv.Itoa(root.Val)
m[subtree]++
if m[subtree] == 2 {
*result = append(*result, root)
}
return subtree
}LC 297. Serialize and Deserialize Binary Tree 二叉树的序列化与反序列化
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/
前序
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type Codec struct {
}
func Constructor() Codec {
return Codec{}
}
// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
if root == nil {
return "#"
}
return strconv.Itoa(root.Val) + "," + this.serialize(root.Left) + "," + this.serialize(root.Right)
}
// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
var dfs func(nodes []string) (*TreeNode, int)
dfs = func(nodes []string) (*TreeNode, int) {
if len(nodes) == 0 {
return nil, 0
}
firstNode := nodes[0]
if firstNode == "#" {
return nil, 1
}
left, leftLength := dfs(nodes[1:])
right, rightLength := dfs(nodes[1+leftLength:])
nodeVal, _ := strconv.Atoi(firstNode)
node := &TreeNode{Val: nodeVal, Left: left, Right: right}
return node, 1+leftLength+rightLength
}
nodes := strings.Split(data, ",")
root, _ := dfs(nodes)
return root
}
/**
* Your Codec object will be instantiated and called as such:
* ser := Constructor();
* deser := Constructor();
* data := ser.serialize(root);
* ans := deser.deserialize(data);
*/后序
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type Codec struct {
}
func Constructor() Codec {
return Codec{}
}
// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
if root == nil {
return "#"
}
return this.serialize(root.Left) + "," + this.serialize(root.Right) + "," + strconv.Itoa(root.Val)
}
// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
var dfs func(nodes []string) (*TreeNode, int)
dfs = func(nodes []string) (*TreeNode, int) {
if len(nodes) == 0 {
return nil, 0
}
lastNode := nodes[len(nodes)-1]
if lastNode == "#" {
return nil, 1
}
right, rightLength := dfs(nodes[:len(nodes)-1])
left, leftLength := dfs(nodes[:len(nodes)-1-rightLength])
nodeVal, _ := strconv.Atoi(lastNode)
node := &TreeNode{Val: nodeVal, Left: left, Right: right}
return node, 1+leftLength+rightLength
}
nodes := strings.Split(data, ",")
root, _ := dfs(nodes)
return root
}
/**
* Your Codec object will be instantiated and called as such:
* ser := Constructor();
* deser := Constructor();
* data := ser.serialize(root);
* ans := deser.deserialize(data);
*/层序
二叉搜索树
LC 230. Kth Smallest Element in a BST 二叉搜索树中第K小的元素
https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/
暴力
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func kthSmallest(root *TreeNode, k int) int {
return dfs(root)[k-1]
}
func dfs(root *TreeNode) (result []int) {
if root == nil {
return nil
}
result = dfs(root.Left)
result = append(result, root.Val)
result = append(result, dfs(root.Right)...)
return result
}暴力 + 优化
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func kthSmallest(root *TreeNode, k int) (result int) {
i := 0
var traverse func (root *TreeNode)
traverse = func (root *TreeNode) {
if root == nil {
return
}
traverse(root.Left)
i++
if i == k {
result = root.Val
return
}
traverse(root.Right)
}
traverse(root)
return result
}LC 538. Conert BST to Greater Tree 把二叉搜索树转换为累加树
https://leetcode.com/problems/convert-bst-to-greater-tree/description/
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func convertBST(root *TreeNode) *TreeNode {
var dfs func (root *TreeNode, acc int) int
dfs = func (root *TreeNode, acc int) int {
if root == nil {
return acc
}
newAcc := dfs(root.Right, acc)
root.Val += newAcc
return dfs(root.Left, root.Val)
}
dfs(root, 0)
return root
}LC 98. Validate Binary Search Tree 验证二叉搜索树
https://leetcode.com/problems/validate-binary-search-tree/description/
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isValidBST(root *TreeNode) bool {
return validate(root, math.MinInt, math.MaxInt)
}
func validate(root *TreeNode, minValue, maxValue int) bool {
if root == nil {
return true
}
if root.Val <= minValue || root.Val >= maxValue {
return false
}
return validate(root.Left, minValue, root.Val) && validate(root.Right, root.Val, maxValue)
}