0226._invert_binary_tree.md

Navigation

Links:

1. https://leetcode.com/problems/invert-binary-tree/
2. https://leetcode-cn.com/problems/invert-binary-tree/

Solution 1 递归

    时间复杂度：O(n)
    空间复杂度：O(n)

---

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

Solution 2 BFS

    时间复杂度：O(n)
    空间复杂度：O(n)

---

from collections import deque 
 
class Solution:
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        dq = deque([root])
        
        while dq:
            node = dq.popleft()
            
            if node:
                node.left, node.right = node.right, node.left
                dq.append(node.left)
                dq.append(node.right)
        
        return root

Solution 3 DFS

    时间复杂度：O(n)
    空间复杂度：O(n)

---

from collections import deque 
 
class Solution:
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        stack = [root]
        
        while stack:
            node = stack.pop()
            
            if node:
                node.left, node.right = node.right, node.left
                stack.append(node.right)
                stack.append(node.left)
                
        return root