代码随想录：二叉树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// 前序遍历函数
func preorderTraversal(root *TreeNode) []int {
    var result []int
    traversal(root, &result) // 为了让traversal函数中对result的append操作同步到本函数中，这里需要传切片的地址
    return result
}
func traversal(node *TreeNode, result *[]int) {
    if node == nil { // 确定递归的出口
       return
    }
    // 先将当前节点的值加入结果列表
    *result = append(*result, node.Val)
    // 然后递归遍历左子树
    traversal(node.Left, result)
    // 最后递归遍历右子树
    traversal(node.Right, result)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func preorderTraversal(root *TreeNode) []int {
    stack := make(map[int]*TreeNode) // map模拟栈
    result := make([]int, 0)
    stack[0] = root
    for len(stack) != 0 {
       topNode := stack[len(stack)-1]
       delete(stack, len(stack)-1)
       if topNode != nil {
          result = append(result, topNode.Val)
       } else {
          continue
       }
       stack[len(stack)] = topNode.Right
       stack[len(stack)] = topNode.Left
    }
    return result
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func inorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)
    traversal(root, &result) // 这里要传地址
    return result
}

// 中序遍历：左中右
func traversal(root *TreeNode, result *[]int) {
    if root == nil {
       return
    }
    traversal(root.Left, result)
    *result = append(*result, root.Val)
    traversal(root.Right, result)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func postorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)
    traversal(root, &result) // 这里要传地址
    return result
}

// 后序遍历：左右中
func traversal(root *TreeNode, result *[]int) {
    if root == nil {
       return
    }
    traversal(root.Left, result)
    traversal(root.Right, result)
    *result = append(*result, 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

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
       return nil
    }
    queue := make([]*TreeNode, 1)
    layerItem := make([]int, 0)
    result := make([][]int, 0)
    queue[0] = root
    for len(queue) != 0 {
       size := len(queue) // 记录每层的元素个数
       layerItem = []int{}
       for size > 0 {
          layerItem = append(layerItem, queue[0].Val) // 将队首元素加入到layerItem中
          if queue[0].Left != nil {
             queue = append(queue, queue[0].Left)
          }
          if queue[0].Right != nil {
             queue = append(queue, queue[0].Right)
          }
          queue = queue[1:] // 去掉队首元素
          size--
       }
       result = append(result, layerItem)
    }
    return result
}

 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

func rightSideView(root *TreeNode) []int {
    if root == nil {
       return nil
    }
    result := make([]int, 0)
    queue := make([]*TreeNode, 1)
    queue[0] = root
    for len(queue) != 0 {
       size := len(queue)
       for size > 0 {
          if size == 1 {
             result = append(result, queue[0].Val) // 将每层最后一个元素加入到result
          }
          if queue[0].Left != nil {
             queue = append(queue, queue[0].Left)
          }
          if queue[0].Right != nil {
             queue = append(queue, queue[0].Right)
          }
          queue = queue[1:] // 弹出队首元素
          size--
       }
    }
    return result
}

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

func levelOrder(root *Node) [][]int {
    if root == nil {
       return nil
    }
    queue := make([]*Node, 1)
    result := make([][]int, 0)
    layerItem := make([]int, 0)
    queue[0] = root
    for len(queue) != 0 {
       layerItem = []int{}
       size := len(queue)
       for size > 0 {
          layerItem = append(layerItem, queue[0].Val)
          if queue[0].Children != nil {
             queue = append(queue, queue[0].Children...)
          }
          queue = queue[1:]
          size--
       }
       result = append(result, layerItem)
    }
    return result
}

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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func minDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	left := minDepth(root.Left)
	right := minDepth(root.Right)
	if left == 0 || right == 0 {  // 注意处理单边二叉树的问题
		return max(left, right) + 1
	}
	return min(left, right) + 1
}

1
2
3
4
5
6
7
8
9

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
       return root
    }
    root.Left, root.Right = root.Right, root.Left
    invertTree(root.Left)
    invertTree(root.Right)
    return root
}

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

func isSymmetric(root *TreeNode) bool {
    if root == nil {
       return true
    }
    return compare(root.Left, root.Right)
}
func compare(left, right *TreeNode) bool {
    if left == nil && right != nil { // 把判空条件写在前面，防止后面出现空指针异常
       return false
    } else if left != nil && right == nil {
       return false
    } else if left == nil && right == nil {
       return true
    } else if left.Val != right.Val { // 这里left不可能为空指针
       return false
    } else { // 左右都不为空的情况，应该递归调用compare函数，比较左右孩子是否对称
       // 左结点的左孩子 vs 右结点的右孩子 && 左结点的右孩子 vs 右结点的左孩子
       return compare(left.Left, right.Right) && compare(left.Right, right.Left)
    }
}

1
2
3
4
5
6

func countNodes(root *TreeNode) int {
    if root == nil {
       return 0
    }
    return countNodes(root.Left) + countNodes(root.Right) + 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 {
    if root == nil {
       return 0
    }
    left := root.Left
    right := root.Right
    leftDepth := 0
    rightDepth := 0
    for left != nil {
       left = left.Left
       leftDepth++
    }
    for right != nil {
       right = right.Right
       rightDepth++
    }
    if leftDepth == rightDepth { // 是满二叉树
       return 2<<leftDepth - 1 // 使用左移来实现乘方的效果
    }
    return countNodes(root.Left) + countNodes(root.Right) + 1
}

 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 isBalanced(root *TreeNode) bool {
    if root == nil {
       return true
    }
    if treeDepth(root.Left) == -1 || treeDepth(root.Right) == -1 { // 注意这里添加这个条件
       return false
    }
    if math.Abs(float64(treeDepth(root.Left)-treeDepth(root.Right))) > 1 {
       return false
    }
    return true
}

func treeDepth(root *TreeNode) int {
    if root == nil {
       return 0
    }
    lDepth := treeDepth(root.Left)
    if lDepth == -1 {
       return -1
    }
    rDepth := treeDepth(root.Right)
    if rDepth == -1 {
       return -1
    }
    if math.Abs(float64(lDepth-rDepth)) > 1 {
       return -1
    } else {
       return max(lDepth, rDepth) + 1
    }
}

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

func binaryTreePaths(root *TreeNode) []string {
    res := make([]string, 0)
    var travel func(node *TreeNode, s string)
    travel = func(node *TreeNode, s string) {
       if node.Left == nil && node.Right == nil { // 递归出口：node为叶子结点
          v := s + strconv.Itoa(node.Val) // 叶子结点的值也需要加上，而且后面不加"->"
          res = append(res, v)
          return // 遇到叶子结点时，需要进行回溯，直接向上层递归返回
       }
       // 这里是前序遍历（深度优先遍历），中右左
       s = s + strconv.Itoa(node.Val) + "->" // s表示当前已经遍历过的路径
       if node.Left != nil {                 // 左结点不为空，继续遍历左结点
          travel(node.Left, s) // 递归遍历node的左孩子
       }
       if node.Right != nil { // 右结点不为空，继续遍历右结点
          travel(node.Right, s)
       }
    }
    travel(root, "") //
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func sumOfLeftLeaves(root *TreeNode) int {
    if root == nil {
       return 0
    }
    // 只递归到非叶子结点（因为非叶子节点才能确定它的左孩子）
    // 我们无法通过某个几点判断它是左孩子还是右孩子，所以递归到叶子结点也没有意义
    if root.Left == nil && root.Right == nil {
       return 0
    }
    lSum := sumOfLeftLeaves(root.Left)
    rSum := sumOfLeftLeaves(root.Right)
    if root.Left != nil && root.Left.Left == nil && root.Left.Right == nil {
       lSum = root.Left.Val // 这里只是记录目标值，不做任何返回，以实现下次递归的复用
    }
    return lSum + rSum
}

 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 findBottomLeftValue(root *TreeNode) int {
    maxDepth := -1
    target := 0
    var traversal = func(node *TreeNode, depth int) {}
    traversal = func(node *TreeNode, depth int) {
       if node.Left == nil && node.Right == nil {
          if depth > maxDepth {
             maxDepth = depth
             target = node.Val
          }
       }
       if node.Left != nil {
          traversal(node.Left, depth+1)
          // 这里将回溯的过程隐藏在了第二个参数里面
          // 也就是往后递归一层的时候，depth加1了，但这个加1操作只对下层的递归有效，
          // 当回溯到本层的时候，depth值是不变的
       }
       if node.Right != nil {
          traversal(node.Right, depth+1)
       }
    }
    traversal(root, 1)
    return target
}

 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

func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
       return false
    }
    var traversal func(node *TreeNode, sum int) bool
    traversal = func(node *TreeNode, sum int) bool {
       if node.Left == nil && node.Right == nil {
          if targetSum == sum+node.Val {
             return true // 向上层返回true
          }
       }
       sum += node.Val
       if node.Left != nil {
          // 当某层递归返回true时，直接向上层返回true，否则不做返回，继续递归
          // 注意：这不能直接写成 return traversal(node.Left, sum)
          if traversal(node.Left, sum) {
             return true
          }
       }
       if node.Right != nil {
          if traversal(node.Right, sum) {
             return true
          }
       }
       return false
    }
    return traversal(root, 0)
}

 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 constructMaximumBinaryTree(nums []int) *TreeNode {
    if nums == nil {
       return nil
    }
    if len(nums) == 1 {
       return &TreeNode{nums[0], nil, nil}
    }
    maxVal := nums[0]
    maxIndex := 0
    for i := 1; i < len(nums); i++ {
       if nums[i] > maxVal {
          maxVal = nums[i]
          maxIndex = i
       }
    }
    curNode := &TreeNode{maxVal, nil, nil} // 中
    if maxIndex > 0 {
       curNode.Left = constructMaximumBinaryTree(nums[0:maxIndex]) // 左闭右开区间
    }
    if maxIndex < len(nums)-1 {
       curNode.Right = constructMaximumBinaryTree(nums[maxIndex+1:])
    }
    return curNode
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    // 构造二叉树我们都使用前序遍历（中左右）
    // 递归出口
    if root1 == nil { // 这里也包含了root1和root2同时为空的情况，返回nil
       return root2
    }
    if root2 == nil {
       return root1
    }
    root1.Val = root1.Val + root2.Val // 把两个二叉树合并到root1上
    root1.Left = mergeTrees(root1.Left, root2.Left)
    root1.Right = mergeTrees(root1.Right, root2.Right)
    return root1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func searchBST1(root *TreeNode, val int) *TreeNode {
    if root == nil || root.Val == val {
       return root
    }
    var result *TreeNode
    if val > root.Val {
       result = searchBST1(root.Right, val)
    } else {
       result = searchBST1(root.Left, val)
    }
    return result
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func searchBST2(root *TreeNode, val int) *TreeNode {
    for root != nil {
       if val == root.Val {
          return root
       }
       if val > root.Val { // 往右搜索
          root = root.Right
       } else {
          root = root.Left
       }
    }
    return root
}

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

func isValidBST1(root *TreeNode) bool {
    result := make([]int, 0)
    var traversal func(node *TreeNode, result *[]int)
    traversal = func(node *TreeNode, result *[]int) {
       if node == nil {
          return
       }
       traversal(node.Left, result)
       *result = append(*result, node.Val)
       traversal(node.Right, result)
    }
    traversal(root, &result)
    for i := 1; i < len(result); i++ {
       if result[i] <= result[i-1] { // 注意，这里等于也要返回false
          return false
       }
    }
    return true
}

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

func isValidBST2(root *TreeNode) bool {
    // 由于Leetcode上面不允许定义全局变量（容易遇到不可知的错误），所以这里只能定义为局部变量，然后再定义一层函数调用
    var maxVal = math.MinInt64 // 记录遍历过的最大的数值
    var traversal func(root *TreeNode) bool
    traversal = func(root *TreeNode) bool {
       if root == nil {
          return true
       }
       var lValid, rValid bool
       lValid = traversal(root.Left) // 左
       if root.Val > maxVal {        // 中
          maxVal = root.Val
       } else {
          return false
       }
       rValid = traversal(root.Right) // 右
       return lValid && rValid
    }
    return traversal(root)
}

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

func getMinimumDifference(root *TreeNode) int {
    var traversal func(node *TreeNode)
    var minDiff = math.MaxInt
    var pre *TreeNode
    traversal = func(cur *TreeNode) {
       if cur == nil {
          return
       }
       // 中序遍历：左中右
       traversal(cur.Left)
       if pre != nil {
          if math.Abs(float64(cur.Val-pre.Val)) < float64(minDiff) {
             minDiff = int(math.Abs(float64(cur.Val - pre.Val)))
          }
       }
       pre = cur
       traversal(cur.Right)
    }
    traversal(root)
    return minDiff
}