0226._invert_binary_tree.md

226. Invert Binary Tree

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/invert-binary-tree/description/

内容描述

Invert a binary tree.

Example:

Input:

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

     4
   /   \
  7     2
 / \   / \
9   6 3   1
Trivia:
This problem was inspired by this original tweet by Max Howell:

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

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

典型的递归题

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return root
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root