『代码随想录』二叉树（Binary Tree）

DAY 14

稍微又复习了一遍二叉树的基础

---

144.二叉树的前序遍历

func preorderTraversal(root *TreeNode) []int {
	if root == nil {
		return []int{}
	}
	ans := []int{root.Val}
	ans = append(ans, preorderTraversal(root.Left)...)
	ans = append(ans, preorderTraversal(root.Right)...)
	return ans
}

当然你还可以压行，就是可读性不行

func preorderTraversal(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    return append([]int{root.Val},append(preorderTraversal(root.Left),preorderTraversal(root.Right)...)...)
}

---

94.二叉树的中序遍历

func inorderTraversal(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    ans := inorderTraversal(root.Left)
    ans = append(ans, root.Val)
    ans = append(ans, inorderTraversal(root.Right)...)
    return ans
}

---

145.二叉树的后序遍历

func postorderTraversal(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    ans := postorderTraversal(root.Left)
    ans = append(ans, postorderTraversal(root.Right)...)
    ans = append(ans, root.Val)
    return ans
}

DAY 15

102. 二叉树的层序遍历

基本思路就是 BFS，使用新旧两个队列轮替遍历

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }

    ans := [][]int{}
    queue := []*TreeNode{root}

    for len(queue) != 0 {
        nextQueue := []*TreeNode{}
        tmp := []int{}

        for len(queue) != 0 {
            curr := queue[0]
            queue = queue[1:]
            tmp = append(tmp, curr.Val)
            if curr.Left != nil {
                nextQueue = append(nextQueue, curr.Left)
            }
            if curr.Right != nil {
                nextQueue = append(nextQueue, curr.Right)
            }
        }

        ans = append(ans, tmp)
        queue = nextQueue
    }
    return ans
}

---

107.二叉树的层序遍历 II

和上一题相同，但是顺序是从下往上

我的第一反应是在上一题最后直接在来个 reverse 哈哈哈

for i := 0; i < len(ans)/2; i++ {
    ans[len(ans)-i-1], ans[i] = ans[i], ans[len(ans)-i-1]
}

或者在插入 ans 的时候在头部插入

然后想其他解法，可以在 DFS 的时候 context 传个当前层数

但…最开始需要的是最底层，我一开始并不知道树高是多少哇

所以一开始还得拿到个层高

感觉不够优雅😰，不写了

---

一些衍生题目，都是层序遍历改一改

199. 二叉树的右视图

- func levelOrder(root *TreeNode) [][]int {
+ func rightSideView(root *TreeNode) []int {
      if root == nil {
          return nil
      }

-   ans := [][]int{}
+   ans := []int{}
      queue := []*TreeNode{root}

      for len(queue) != 0 {
          nextQueue := []*TreeNode{}
-         tmp := []int{}
+         tmp := 0

          for len(queue) != 0 {
              curr := queue[0]
              queue = queue[1:]
-            tmp = append(tmp, curr.Val)
+            tmp = curr.Val
              if curr.Left != nil {
                  nextQueue = append(nextQueue, curr.Left)
              }
              if curr.Right != nil {
                  nextQueue = append(nextQueue, curr.Right)
              }
          }

          ans = append(ans, tmp)
          queue = nextQueue
      }
      return ans
  }

637. 二叉树的层平均值

- func levelOrder(root *TreeNode) [][]int {
+ func averageOfLevels(root *TreeNode) []float64 {
    if root == nil {
        return nil
    }

-   ans := [][]int{}
+   ans := []float64{}
    queue := []*TreeNode{root}

    for len(queue) != 0 {
        nextQueue := []*TreeNode{}
        tmp := []int{}

        for len(queue) != 0 {
            curr := queue[0]
            queue = queue[1:]
            tmp = append(tmp, curr.Val)
            if curr.Left != nil {
                nextQueue = append(nextQueue, curr.Left)
            }
            if curr.Right != nil {
                nextQueue = append(nextQueue, curr.Right)
            }
        }

-       ans = append(ans, tmp)
+       ans = append(ans, func(nums []int) float64 {
+           sum := 0
+           for _, v := range nums {
+               sum += v
+           }
+           return float64(sum) / float64(len(nums))
+       }(tmp))
        queue = nextQueue
    }
    return ans
  }

429. N 叉树的层序遍历

- func levelOrder(root *TreeNode) [][]int {
+ func levelOrder(root *Node) [][]int {
  	if root == nil {
  		return nil
  	}

  	ans := [][]int{}
- 	queue := []*TreeNode{root}
+ 	queue := []*Node{root}

  	for len(queue) != 0 {
- 		nextQueue := []*TreeNode{}
+ 		nextQueue := []*Node{}
  		tmp := []int{}

  		for len(queue) != 0 {
  			curr := queue[0]
  			queue = queue[1:]
  			tmp = append(tmp, curr.Val)
- 			if curr.Left != nil {
- 				nextQueue = append(nextQueue, curr.Left)
- 			}
- 			if curr.Right != nil {
- 				nextQueue = append(nextQueue, curr.Right)
+
+ 			for _, c := range curr.Children {
+ 				nextQueue = append(nextQueue, c)
  			}
  		}

  		ans = append(ans, tmp)
  		queue = nextQueue
  	}
  	return ans
  }

515. 在每个树行中找最大值

- func levelOrder(root *TreeNode) [][]int {
+ func largestValues(root *TreeNode) []int {
    if root == nil {
        return nil
    }

-   ans := [][]int{}
+   ans := []int{}
    queue := []*TreeNode{root}

    for len(queue) != 0 {
        nextQueue := []*TreeNode{}
-       tmp := []int{}
+       tmp := math.MinInt

        for len(queue) != 0 {
            curr := queue[0]
            queue = queue[1:]
-           tmp = append(tmp, curr.Val)
+           if curr.Val > tmp {
+               tmp = curr.Val
+           }
            if curr.Left != nil {
                nextQueue = append(nextQueue, curr.Left)
            }
            if curr.Right != nil {
                nextQueue = append(nextQueue, curr.Right)
            }
        }

        ans = append(ans, tmp)
        queue = nextQueue
    }
    return ans
  }

116. 填充每个节点的下一个右侧节点指针

- func levelOrder(root *TreeNode) [][]int {
+ func connect(root *Node) *Node {
    if root == nil {
        return nil
    }

-   ans := [][]int{}
-   queue := []*TreeNode{root}
+   queue := []*Node{root}

    for len(queue) != 0 {
-       nextQueue := []*TreeNode{}
+       nextQueue := []*Node{}
+       prev := &Node{}
-       tmp := []int{}
-
        for len(queue) != 0 {
            curr := queue[0]
            queue = queue[1:]
-           tmp = append(tmp, curr.Val)
+           prev.Next = curr
+           prev = curr
            if curr.Left != nil {
                nextQueue = append(nextQueue, curr.Left)
            }
            if curr.Right != nil {
                nextQueue = append(nextQueue, curr.Right)
            }
        }
-
-       ans = append(ans, tmp)
        queue = nextQueue
    }
-   return ans
+   return root
  }

117. 填充每个节点的下一个右侧节点指针 II

与上题完全一样

104. 二叉树的最大深度

- func levelOrder(root *TreeNode) [][]int {
+ func maxDepth(root *TreeNode) int {
    if root == nil {
-       return nil
+       return 0
    }

-   ans := [][]int{}
+   count := 0
+   ans := 0
    queue := []*TreeNode{root}

    for len(queue) != 0 {
+       count++
        nextQueue := []*TreeNode{}
-       tmp := []int{}
-
        for len(queue) != 0 {
            curr := queue[0]
            queue = queue[1:]
-           tmp = append(tmp, curr.Val)
            if curr.Left != nil {
                nextQueue = append(nextQueue, curr.Left)
            }
            if curr.Right != nil {
                nextQueue = append(nextQueue, curr.Right)
            }
+           if curr.Right == nil && curr.Left == nil && count > ans {
+               ans = count
+           }
        }

-       ans = append(ans, tmp)
        queue = nextQueue
    }
    return ans
  }

111. 二叉树的最小深度

- func levelOrder(root *TreeNode) [][]int {
+ func minDepth(root *TreeNode) int {
    if root == nil {
-       return nil
+       return 0
    }

-   ans := [][]int{}
+   count := 0
+   ans := math.MaxInt
    queue := []*TreeNode{root}

    for len(queue) != 0 {
+       count++
        nextQueue := []*TreeNode{}
-       tmp := []int{}
-
        for len(queue) != 0 {
            curr := queue[0]
            queue = queue[1:]
-           tmp = append(tmp, curr.Val)
            if curr.Left != nil {
                nextQueue = append(nextQueue, curr.Left)
            }
            if curr.Right != nil {
                nextQueue = append(nextQueue, curr.Right)
            }
+           if curr.Right == nil && curr.Left == nil && count < ans {
+               ans = count
+               return ans
+           }
        }

-       ans = append(ans, tmp)
        queue = nextQueue
    }
    return ans
  }

附：`diff.py`

import difflib

def calculate_diff(file1_path, file2_path, output_path):
    # Read the contents of the two files
    with open(file1_path, 'r') as f1, open(file2_path, 'r') as f2:
        file1_content = f1.readlines()
        file2_content = f2.readlines()

    # Calculate the diff
    diff = difflib.ndiff(file1_content, file2_content)

    # Filter out the lines that only contain changes in whitespace or question marks
    filtered_diff = [line for line in diff if not line.startswith('?')]

    # Convert the diff to markdown format
    markdown_diff = '```diff\n' + ''.join(filtered_diff) + '```'

    # Write the markdown diff to the output file
    with open(output_path, 'w') as output_file:
        output_file.write(markdown_diff)

# Example usage:
calculate_diff('main.go', 'diff.go', 'diff_output.md')

---

101.对称二叉树

第一反应：嗯？

第二反应：左侧用「左中右」遍历，右侧用「右中左」遍历，然后比较行不行？

第三反应：将一侧的左右儿子递归地反转，然后和另一侧比较是不是完全一样

但是这样感觉太麻烦了，我递归的时候直接镜像比较行不行（左边的左儿子比较右边的右儿子）

func isSymmetric(root *TreeNode) bool {
    return myIsSymmet(root.Left, root.Right)
}

func myIsSymmet(left *TreeNode, right *TreeNode) bool {
    if left == nil && right == nil {
        return true
    } else if (left == nil && right != nil) || (left != nil && right == nil) || left.Val != right.Val {
        return false
    }

    return myIsSymmet(left.Left, right.Right) && myIsSymmet(left.Right, right.Left)
}

---

226.翻转二叉树

好好好

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return root
    }

    invertTree(root.Left)
    invertTree(root.Right)

    root.Left, root.Right = root.Right, root.Left
    return root
}

DAY 16

104.二叉树的最大深度

试一下递归的写法

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

---

111.二叉树的最小深度

本来想这么写

func minDepth(root *TreeNode) int {
    if root == nil {
        return math.MaxInt
    } else if root.Left == nil && root.Right == nil {
        return 1
    }
    return min(minDepth(root.Left), minDepth(root.Right)) + 1
}

但是如果 root 是 nil 就有问题

func minDepth(root *TreeNode) int {
    switch {
    case root == nil:
        return 0
    case root.Left == nil && root.Right == nil:
        return 1
    case root.Left != nil && root.Right == nil:
        return minDepth(root.Left) + 1
    case root.Right != nil && root.Left == nil:
        return minDepth(root.Right) + 1
    default:
        return min(minDepth(root.Left), minDepth(root.Right)) + 1
    }
}

---

222.完全二叉树的节点个数

先来个暴力 O(n) 的

func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return countNodes(root.Left) + countNodes(root.Right) + 1
}

我想利用完全二叉树的特性，遍历时最后层顺序是从左往右，如果遇到 nil 就直接结束

但是貌似还是不够快

func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }
    maxDepth := getDepth(root)
    ans := 1<<(maxDepth-1) - 1
    var dfs func(root *TreeNode, depth int) bool
    dfs = func(root *TreeNode, depth int) bool {
        if root == nil {
            return true
        }
        if depth == maxDepth {
            ans++
            return false
        }
        if dfs(root.Left, depth+1) {
            return true
        }
        if dfs(root.Right, depth+1) {
            return true
        }
        return false
    }
    dfs(root, 1)
    return ans
}

func getDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return getDepth(root.Left) + 1
}

然后我去看了题解，可以比较左右深度来判断是否是满二叉树，如果是满二叉树则可以直接计算节点个数

func countNodes(root *TreeNode) int {
    leftDepth, rightDepth := getLeftDepth(root), getRightDepth(root)
    if leftDepth == rightDepth {
        return (1 << leftDepth) - 1
    }
    return countNodes(root.Left) + countNodes(root.Right) + 1
}

func getLeftDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return getLeftDepth(root.Left) + 1
}

func getRightDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return getRightDepth(root.Right) + 1
}

DAY 17

110.平衡二叉树

看题目以为是写平衡树，进来发现是判断是否是平衡树

我本来想检查所有叶子节点是否在两层中，但是这样实际上是有问题的

func isBalanced(root *TreeNode) bool {
    m := make(map[int]bool)

    var dfs func(root *TreeNode, depth int)
    dfs = func(root *TreeNode, depth int) {
        if root == nil {
            return
        } else if root.Left == nil && root.Right == nil {
            m[depth] = true
        }
        dfs(root.Left, depth+1)
        dfs(root.Right, depth+1)
    }
    dfs(root, 0)
    fmt.Println(m)
    return len(m) <= 2
}

好吧，还得按照定义去做

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    if abs(getDepth(root.Left)-getDepth(root.Right)) > 1 {
        return false
    }
    return isBalanced(root.Left) && isBalanced(root.Right)
}

func getDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(getDepth(root.Left), getDepth(root.Right)) + 1
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

但是这会涉及到重复计算，我感觉能不能优化一下

func isBalanced(root *TreeNode) bool {
    ans := true

    var dfs func(root *TreeNode) int
    dfs = func(root *TreeNode) int {
        if root == nil {
            return 0
        }

        depL, depR := dfs(root.Left), dfs(root.Right)
        if ans == false || abs(depL-depR) > 1 {
            ans = false
            return -1
        }
        return max(depL, depR) + 1
    }
    dfs(root)

    return ans
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

---

257.二叉树的所有路径

func binaryTreePaths(root *TreeNode) []string {
    ans := []string{}

    if root == nil {
        return ans
    } else if root.Left == nil && root.Right == nil {
        return []string{fmt.Sprintf("%d", root.Val)}
    }

    var dfs func(curr *TreeNode, s string)
    dfs = func(curr *TreeNode, s string) {
        s = s + "->" + fmt.Sprintf("%d", curr.Val)

        if curr.Left == nil && curr.Right == nil {
            ans = append(ans, s)
        }
        if curr.Left != nil {
            dfs(curr.Left, s)
        }
        if curr.Right != nil {
            dfs(curr.Right, s)
        }
    }
    if root.Left != nil {
        dfs(root.Left, fmt.Sprintf("%d", root.Val))
    }
    if root.Right != nil {
        dfs(root.Right, fmt.Sprintf("%d", root.Val))
    }
    return ans
}

---

404.左叶子之和

func sumOfLeftLeaves(root *TreeNode) int {
    if root == nil {
        return 0
    }
    if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil {
        return root.Left.Val + sumOfLeftLeaves(root.Right)
    }
    return sumOfLeftLeaves(root.Right) + sumOfLeftLeaves(root.Left)
}

DAY 18

513.找树左下角的值

最底层最左边，先来一手层序遍历

func findBottomLeftValue(root *TreeNode) int {
    queue := []*TreeNode{root}
    ans := 0
    ansFlag := false

    for len(queue) != 0 {
        nextQueue := []*TreeNode{}
        ansFlag = false

        for len(queue) != 0 {
            curr := queue[0]
            queue = queue[1:]

            if ansFlag == false {
                ans = curr.Val
                ansFlag = true
            }

            if curr.Left != nil {
                nextQueue = append(nextQueue, curr.Left)
            }
            if curr.Right != nil {
                nextQueue = append(nextQueue, curr.Right)
            }
        }
        queue = nextQueue
    }
    return ans
}

再写一个递归的

func findBottomLeftValue(root *TreeNode) int {
    maxDepth := -1
    ans := 0

    var dfs func(curr *TreeNode, depth int)
    dfs = func(curr *TreeNode, depth int) {
        if curr == nil {
            return
        }

        if depth > maxDepth {
            maxDepth = depth
            ans = curr.Val
        }

        dfs(curr.Left, depth+1)
        dfs(curr.Right, depth+1)
    }

    dfs(root, 0)
    return ans
}

---

112.路径总和

func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }
    if root.Left == nil && root.Right == nil && targetSum == root.Val {
        return true
    }
    return hasPathSum(root.Left, targetSum-root.Val) || hasPathSum(root.Right, targetSum-root.Val)
}

---

113. 路径总和 II

记得在保存答案的时候要创建副本，不然会被后面的递归修改

func pathSum(root *TreeNode, targetSum int) [][]int {
    ans := [][]int{}

    var dfs func(path []int, root *TreeNode, targetSum int)
    dfs = func(path []int, root *TreeNode, targetSum int) {
        if root == nil {
            return
        }
        path = append(path, root.Val)

        if root.Left == nil && root.Right == nil && targetSum == root.Val {
            ans = append(ans, append([]int{}, path...)) // 创建路径的副本
            return
        }

        dfs(path, root.Left, targetSum-root.Val)
        dfs(path, root.Right, targetSum-root.Val)
    }

    dfs([]int{}, root, targetSum)
    return ans
}

除了使用 append 之外，你还可以使用 copy ，注意一定是 make([]int,len(path)) ，[]int{} 与 make([]int,0,len(path)) 都是不可以的

tmp:=make([]int,len(path))
copy(tmp,path)
ans = append(ans, tmp)

---

106.从中序与后序遍历序列构造二叉树

把握好遍历顺序，找到中点然后拆解递归

// 左 中 右
// 左 右 中
func buildTree(inorder []int, postorder []int) *TreeNode {
    n := len(inorder)
    if n == 0 {
        return nil
    }

    midVal, midIdx := postorder[n-1], 0
    for inorder[midIdx] != midVal {
        midIdx++
    }

    leftInorder := inorder[:midIdx]
    leftPostorder := postorder[:midIdx]
    rightInorder := inorder[midIdx+1:]
    rightPostorder := postorder[midIdx : n-1]

    return &TreeNode{
        Val:   midVal,
        Left:  buildTree(leftInorder, leftPostorder),
        Right: buildTree(rightInorder, rightPostorder),
    }
}

---

105.从前序与中序遍历序列构造二叉树

// 中 左 右
// 左 中 右
func buildTree(preorder []int, inorder []int) *TreeNode {
    n := len(preorder)
    if n == 0 {
        return nil
    }

    midVal, midIdx := preorder[0], 0
    for inorder[midIdx] != midVal {
        midIdx++
    }

    leftPreorder := preorder[1 : 1+midIdx]
    leftInorder := inorder[:midIdx]
    rightPreorder := preorder[1+midIdx:]
    rightInorder := inorder[midIdx+1:]

    return &TreeNode{
        Val:   midVal,
        Left:  buildTree(leftPreorder, leftInorder),
        Right: buildTree(rightPreorder, rightInorder),
    }
}

DAY 19

周日休息

DAY 20

617.合并二叉树

写完看了眼题解发现我写的太复杂了（

func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil && root2 == nil {
        return nil
    }

    ans := &TreeNode{}
    if root1 != nil {
        ans.Val += root1.Val
    }
    if root2 != nil {
        ans.Val += root2.Val
    }

    if root1 == nil && root2 != nil {
        ans.Left = mergeTrees(nil, root2.Left)
        ans.Right = mergeTrees(nil, root2.Right)
    } else if root1 != nil && root2 == nil {
        ans.Left = mergeTrees(root1.Left, nil)
        ans.Right = mergeTrees(root1.Right, nil)
    } else {
        ans.Left = mergeTrees(root1.Left, root2.Left)
        ans.Right = mergeTrees(root1.Right, root2.Right)
    }

    return ans
}

func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil {
        return root2
    } else if root2 == nil {
        return root1
    }

    root1.Val += root2.Val
    root1.Left = mergeTrees(root1.Left, root2.Left)
    root1.Right = mergeTrees(root1.Right, root2.Right)
    return root1
}

---

700.二叉搜索树中的搜索

func searchBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return nil
    } else if root.Val == val {
        return root
    }

    if val < root.Val {
        return searchBST(root.Left, val)
    }
    return searchBST(root.Right, val)
}

---

654.最大二叉树

func constructMaximumBinaryTree(nums []int) *TreeNode {
    if len(nums) == 0 {
        return nil
    }
    maxVal, maxIdx := getMax(nums)
    return &TreeNode{
        Val:   maxVal,
        Left:  constructMaximumBinaryTree(nums[:maxIdx]),
        Right: constructMaximumBinaryTree(nums[maxIdx+1:]),
    }
}

func getMax(nums []int) (maxVal, maxIdx int) {
    maxVal = math.MinInt
    for idx, val := range nums {
        if val > maxVal {
            maxVal = val
            maxIdx = idx
        }
    }
    return
}

---

98.验证二叉搜索树

两种思路，一种使用中序遍历必定单调的性质，一种检查左右子树的边界

func isValidBST(root *TreeNode) bool {
    prevVal := math.MinInt
    ans := true
    var dfs func(root *TreeNode)
    dfs = func(root *TreeNode) {
        if ans == false || root == nil {
            return
        }
        dfs(root.Left)
        if root.Val <= prevVal {
            ans = false
            return
        }
        prevVal = root.Val
        dfs(root.Right)
    }
    dfs(root)
    return ans
}

边界检查

func isValidBST(root *TreeNode) bool {
    return myIsValidBST(root, math.MinInt, math.MaxInt)
}

func myIsValidBST(root *TreeNode, minVal, maxVal int) bool {
    if root == nil {
        return true
    }

    if root.Val <= minVal || root.Val >= maxVal {
        return false
    }

    leftIsValid := myIsValidBST(root.Left, minVal, root.Val)
    rightIsValid := myIsValidBST(root.Right, root.Val, maxVal)

    return leftIsValid && rightIsValid
}

DAY 21

530.二叉搜索树的最小绝对差

使用搜索树中序遍历是单调的性质

func getMinimumDifference(root *TreeNode) int {
    nums := []int{}
    var dfs func(root *TreeNode)
    dfs = func(root *TreeNode) {
        if root == nil {
            return
        }
        dfs(root.Left)
        nums = append(nums, root.Val)
        dfs(root.Right)
    }
    dfs(root)

    ans := math.MaxInt
    for i := 1; i < len(nums); i++ {
        ans = min(ans, abs(nums[i]-nums[i-1]))
    }
    return ans
}

---

501.二叉搜索树中的众数

最暴力的方法

func findMode(root *TreeNode) []int {
    nums := []int{}
    var dfs func(root *TreeNode)
    dfs = func(root *TreeNode) {
        if root == nil {
            return
        }
        dfs(root.Left)
        nums = append(nums, root.Val)
        dfs(root.Right)
    }
    dfs(root)

    ans := []int{}
    m := map[int]int{}
    for _, num := range nums {
        m[num]++
    }

    maxV := 0
    for _, v := range m {
        if v > maxV {
            maxV = v
        }
    }

    for k, v := range m {
        if v == maxV {
            ans = append(ans, k)
        }
    }

    return ans
}

还可以用单调的性质节省掉哈希表

prev := math.MinInt
count := 0
maxCount := 0
ans := []int{}
for _, v := range nums {
    if v == prev {
        count++
    } else {
        prev = v
        count = 1
    }

    if count == maxCount {
        ans = append(ans, v)
    } else if count > maxCount {
        maxCount = count
        ans = []int{v}
    }
}

---

236.二叉树的最近公共祖先

1. 基础情况:
   • 如果当前节点是nil，说明已经到达了树的底部，返回nil。
   • 如果当前节点是p或q中的任意一个，那么它可能是最低公共祖先，返回这个节点。
2. 递归查找:
   • 对当前节点的左子树调用lowestCommonAncestor函数，查找p和q。
   • 对当前节点的右子树同样调用lowestCommonAncestor函数。
3. 分析递归结果:
   • 如果在左子树和右子树的搜索结果中，两边都找到了节点（即左右子树各返回了非nil），则说明当前节点是最低公共祖先。
   • 如果只在一边找到了节点（左子树或右子树返回了非nil），则最低公共祖先在那一边。

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    if root == q || root == p {
        return root
    }

    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)

    if left != nil && right != nil {
        return root
    } else if left == nil && right != nil {
        return right
    } else {
        return left
    }
}

DAY 22

235.二叉搜索树的最近公共祖先

我本来想用搜索树的性质做一个剪枝，也就是如果当前节点的值不在两者之间，就肯定不可能是祖先

if p.Val > q.Val {
    p,q = q,p
}
if root.Val < q.Val || root.Val > p.Val{
    return nil
}

但是这是错误的，当前节点的确不会是最近公共祖先，但是下面的节点可能是，应该继续递归

这个性质应该这样用

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }

    // 如果p和q的值都小于root的值，LCA在左子树
    if p.Val < root.Val && q.Val < root.Val {
        return lowestCommonAncestor(root.Left, p, q)
    }

    // 如果p和q的值都大于root的值，LCA在右子树
    if p.Val > root.Val && q.Val > root.Val {
        return lowestCommonAncestor(root.Right, p, q)
    }

    // 如果root的值介于p和q之间，那么root就是LCA
    return root
}

---

701.二叉搜索树中的插入操作

遵从搜索树的定义即可

func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{Val: val}
    }

    if root.Val < val {
        if root.Right != nil {
            insertIntoBST(root.Right, val)
        } else {
            root.Right = &TreeNode{
                Val: val,
            }
        }
    } else {
        if root.Left != nil {
            insertIntoBST(root.Left, val)
        } else {
            root.Left = &TreeNode{
                Val: val,
            }
        }
    }
    return root
}

---

450. 删除二叉搜索树中的节点

• 当 key < root.Val 时，我们递归地在左子树中删除节点。

• 当 key > root.Val 时，我们递归地在右子树中删除节点。

• 当 key == root.Val 时，我们找到了要删除的节点：

  • 如果是叶子就直接删了了事

  • 如果只有左子树或者右子树，就把左（右）子树接到上面去

  • 如果左右都有，删了之后把左子树的最大值或者右子树的最小值放在当前节点

    具体来说就是把值赋值给当前节点，然后再在左（右）子树中删除这个最大（小）节点

func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return nil
    }
    if key < root.Val { // 如果节点在左边就往左递归
        root.Left = deleteNode(root.Left, key)
    } else if key > root.Val { // 如果节点在右边就往右递归
        root.Right = deleteNode(root.Right, key)
    } else { // 当前就是要删的了！
        if root.Left == nil && root.Right == nil { // 如果是叶子节点，直接删除了事
            return nil
        } else if root.Left == nil { // 如果只有右子树，就把右子树提上来
            return root.Right
        } else if root.Right == nil { // 如果只有左子树，就把左子树提上来
            return root.Left
        } else { // 如果左右子树都有，就找到右子树的最小节点，把值赋给当前节点，然后删除右子树的最小节点
            minVal := findMin(root.Right)
            root.Val = minVal
            root.Right = deleteNode(root.Right, minVal)
        }
    }
    return root
}

func findMin(root *TreeNode) int {
	if root.Left == nil {
        return root.Val
    }
    return findMin(root.Left)
}

DAY 23

669.修剪二叉搜索树

如果出界了就尝试往边界里面走

func trimBST(root *TreeNode, low int, high int) *TreeNode {
    if root == nil {
        return nil
    }

    if root.Val >= low && root.Val <= high {
        root.Left = trimBST(root.Left, low, high)
        root.Right = trimBST(root.Right, low, high)
        return root
    }

    if root.Val < low && root.Right != nil {
        return trimBST(root.Right, low, high)
    } else if root.Val > high && root.Left != nil {
        return trimBST(root.Left, low, high)
    } else {
        return nil
    }
}

---

108.将有序数组转换为二叉搜索树

因为要转换成平衡树，我一开始想先计算树高，后来发现没那么麻烦，直接中间作为根节点，然后左右平分递归下去就行了

因为左右节点数量基本相同，所以是平衡的

func sortedArrayToBST(nums []int) *TreeNode {
    n := len(nums)
    if n == 0 {
        return nil
    }
    mid := n / 2
    return &TreeNode{
        Val:   nums[mid],
        Left:  sortedArrayToBST(nums[:mid]),
        Right: sortedArrayToBST(nums[mid+1:]),
    }
}

---

538.把二叉搜索树转换为累加树

递归感觉被绕晕了，用最暴力的方法，按照中序把值都拿到手，计算好再塞回去（

func convertBST(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }

    ans := []int{}
    var dfs func(root *TreeNode)
    dfs = func(root *TreeNode) {
        if root == nil {
            return
        }
        dfs(root.Left)
        ans = append(ans, root.Val)
        dfs(root.Right)
    }
    dfs(root)

    n := len(ans)
    for i := n - 2; i >= 0; i-- {
        ans[i] += ans[i+1]
    }

    idx := 0
    var dfs2 func(root *TreeNode)
    dfs2 = func(root *TreeNode) {
        if root == nil {
            return
        }
        dfs2(root.Left)
        root.Val = ans[idx]
        idx++
        dfs2(root.Right)
    }
    dfs2(root)

    return root
}

看了眼题解，哦，好吧

func convertBST(root *TreeNode) *TreeNode {
    sum := 0
    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node != nil {
            dfs(node.Right)
            sum += node.Val
            node.Val = sum
            dfs(node.Left)
        }
    }
    dfs(root)
    return root
}