题目描述

[EN | CN]

翻转一棵二叉树。

示例:

输入:

1
2
3
4
5
4
   /   \
  2     7
 / \   / \
1   3 6   9

输出:

1
2
3
4
5
4
   /   \
  7     2
 / \   / \
9   6 3   1

解法 1:递归

简单的递归思路。

假设结点数为 $n$,那么

  • 时间复杂度为 $O(n)$,与每个结点成正比;
  • 空间复杂度为 $O(\log n)$,与树高度有关,平均为 $O(\log n)$,最坏为 $O(n)$。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root is None:
            return
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root
  • 执行用时:44 ms,在所有 Python3 提交中击败了 39.16% 的用户。
  • 内存消耗:13.6 MB,在所有 Python3 提交中击败了 5.26% 的用户。

解法 2:迭代

简单迭代。

复杂度与递归一样。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        trees_to_invert = [root]
        while trees_to_invert:
            node = trees_to_invert.pop()
            if node is not None:
                node.left, node.right = node.right, node.left
                trees_to_invert.extend([node.left, node.right])
        return root
  • 执行用时:40 ms,在所有 Python3 提交中击败了 57.15% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 5.26% 的用户。