代码随想录算法训练营第十三天 | 226、101、104、111

算法
, , ,

226. 翻转二叉树

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    // 交换当前节点的左右子节点
    root.Left, root.Right = root.Right, root.Left
    // 递归处理左右子树
    invertTree(root.Left)
    invertTree(root.Right)
    return root
}

101. 对称二叉树

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
package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return isMirror(root.Left, root.Right)
}

func isMirror(left, right *TreeNode) bool {
    if left == nil && right == nil {
        return true
    }
    if left == nil || right == nil {
        return false
    }
    return (left.Val == right.Val) &&
        isMirror(left.Left, right.Right) &&
        isMirror(left.Right, right.Left)
}

104. 二叉树的最大深度

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

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    leftDepth := maxDepth(root.Left)
    rightDepth := maxDepth(root.Right)
    if leftDepth > rightDepth {
        return leftDepth + 1
    }
    return rightDepth + 1
}

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
package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    // 叶子节点，深度为 1
    if root.Left == nil && root.Right == nil {
        return 1
    }
    // 左子树为空，只能计算右子树
    if root.Left == nil {
        return minDepth(root.Right) + 1
    }
    // 右子树为空，只能计算左子树
    if root.Right == nil {
        return minDepth(root.Left) + 1
    }
    // 左右子树均存在，取较小值
    left := minDepth(root.Left)
    right := minDepth(root.Right)
    if left < right {
        return left + 1
    }
    return right + 1
}