反转二叉树

Invert Binary Tree ⭐️

LeetCode每日一题 2020.09.16

翻转一棵二叉树。

Example:

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

Input:
     4
   /   \
  2     7
 / \   / \
1   3 6   9
Output:
     4
   /   \
  7     2
 / \   / \
9   6 3   1

Trivia: 这道题来源于(Homebrew)作者原问题启发:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

题目大意

题目简单明了, 如上图所示翻转整个二叉树。

解题思路

这题是一个很简答的二叉树问题。显然, 我们从二叉树根节点顶部开始, 对树进行递归遍历, 先交换子节点, 再依次翻转叶子节点(从末端叶子节点先开始翻转也可以)。

代码

递归法

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

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

复杂度分析

• 时间复杂度: $O(n)$, 其中 n 是二叉树中的节点个数。
• 空间复杂度: $O(n)$, 当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 $O(logN)$。而在最坏情况下，树形成链状，空间复杂度为 $O(N)$。

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章