IT博客汇
  • 首页
  • 精华
  • 技术
  • 设计
  • 资讯
  • 扯淡
  • 权利声明
    • 登录 注册

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

    NX の 博客发表于 2023-11-07 11:47:26
    love 0

    DAY 14

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

    144.二叉树的前序遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    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
    }

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

    1
    2
    3
    4
    5
    6
    func preorderTraversal(root *TreeNode) []int {
        if root == nil {
            return []int{}
        }
        return append([]int{root.Val},append(preorderTraversal(root.Left),preorderTraversal(root.Right)...)...)
    }

    94.二叉树的中序遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    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.二叉树的后序遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    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，使用新旧两个队列轮替遍历

    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
    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 哈哈哈

    1
    2
    3
    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. 二叉树的右视图
    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
    - 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. 二叉树的层平均值
    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
    - 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 叉树的层序遍历
    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
    - 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. 在每个树行中找最大值
    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
    - 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. 填充每个节点的下一个右侧节点指针
    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
    - 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. 二叉树的最大深度
    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
    - 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. 二叉树的最小深度
    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
    - 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`
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    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.对称二叉树

    第一反应：嗯？

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

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    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.翻转二叉树

    好好好

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    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.二叉树的最大深度

    试一下递归的写法

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

    111.二叉树的最小深度

    本来想这么写

    1
    2
    3
    4
    5
    6
    7
    8
    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 就有问题

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    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) 的

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

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

    但是貌似还是不够快

    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
    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
    }

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    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.平衡二叉树

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    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
    }

    好吧，还得按照定义去做

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    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
    }

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

    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
    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.二叉树的所有路径

    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
    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.左叶子之和

    1
    2
    3
    4
    5
    6
    7
    8
    9
    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.找树左下角的值

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

    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
    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
    }

    再写一个递归的

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23

    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.路径总和

    1
    2
    3
    4
    5
    6
    7
    8
    9
    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

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    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)) 都是不可以的

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

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    // 左 中 右
    // 左 右 中
    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.从前序与中序遍历序列构造二叉树

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    // 中 左 右
    // 左 中 右
    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.合并二叉树

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

    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
    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
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    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.二叉搜索树中的搜索

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    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.最大二叉树

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    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.验证二叉搜索树

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    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
    }

    边界检查

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    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.二叉搜索树的最小绝对差

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    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.二叉搜索树中的众数

    最暴力的方法

    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
    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
    }

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    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），则最低公共祖先在那一边。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    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.二叉搜索树的最近公共祖先

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

    1
    2
    3
    4
    5
    6
    if p.Val > q.Val {
        p,q = q,p
    }
    if root.Val < q.Val || root.Val > p.Val{
        return nil
    }

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

    这个性质应该这样用

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    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.二叉搜索树中的插入操作

    遵从搜索树的定义即可

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    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 时，我们找到了要删除的节点：

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

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

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

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

    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
    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.修剪二叉搜索树

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    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.将有序数组转换为二叉搜索树

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    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.把二叉搜索树转换为累加树

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

    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
    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
    }

    看了眼题解，哦，好吧

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    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
    }


沪ICP备19023445号-2号
友情链接