226. Invert Binary Tree

Problem

Given the root of a binary tree, invert the tree, and return its root.

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

Example 1:

case1

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

case2

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 3:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Test Cases

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:

solution_test.py

import pytest

import os
import sys
sys.path.append(os.path.dirname(os.path.dirname(__file__)))
from _utils.binary_tree import build_tree, print_tree
from solution import Solution

null = None


@pytest.mark.parametrize('root, expected', [
    ([4,2,7,1,3,6,9], [4,7,2,9,6,3,1]),
    ([2,1,3], [2,3,1]),
    ([], []),
])
class Test:
    def test_solution(self, root, expected):
        sol = Solution()
        result = sol.invertTree(build_tree(root))
        assert print_tree(result) == expected

Thoughts

按任何顺序遍历二叉树，前序（pre-order，NLR），对于当前节点，交换左右子节点即可。

Code

solution.py

from typing import Optional


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


class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        backup = root
        stack = []
        while root or stack:
            if root:
                stack.append(root)
                root.left, root.right = root.right, root.left
                root = root.left # Original right child.
            else:
                root = stack.pop().right # Original left child.

        return backup

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。