LeetCode: 226 Invert Binary Tree

•

admin

Invert a binary tree.

Example:

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

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

问题

翻转一棵二叉树。

解决方案 1

递归方法

Approach 1 / 方法 1

This solution uses a recursive approach. The idea is to swap the left and right child of each node in the binary tree. The function calls itself for the left and right children recursively.

该解决方案使用递归方法。其思想是交换二叉树中每个节点的左右子节点。函数会递归地对左右子节点进行调用。

Implementation / 实现

python

# Solution 1 implementation in Python
def invertTree(root):
    if root is None:
        return None
    root.left, root.right = root.right, root.left
    invertTree(root.left)
    invertTree(root.right)
    return root

Explanation / 解释

  1. Step 1 / 第一步:
  • Check if the root is None. If yes, return None.
    检查根节点是否为空。如果是，返回None。
  1. Step 2 / 第二步:
  • Swap the left and right child of the root.
    交换根节点的左右子节点。
  1. Step 3 / 第三步:
  • Recursively call invertTree on the left and right children.
    递归调用invertTree对左右子节点进行翻转。

Complexity Analysis / 复杂度分析

  • Time Complexity: O(n), where n is the number of nodes in the tree.
    时间复杂度: O(n)，其中n是树中的节点数。

  • Space Complexity: O(h), where h is the height of the tree (due to the recursion stack).
    空间复杂度: O(h)，其中h是树的高度（由于递归调用栈）。

Key Concept / 关键概念

  • Recursive tree traversal and node swapping.
    递归遍历树和节点交换。

解决方案 2

迭代方法

Approach 2 / 方法 2

This solution uses an iterative approach with a queue to traverse the tree level by level. For each node, we swap its children and add them to the queue.

该解决方案使用队列的迭代方法来逐层遍历树。对于每个节点，我们交换其子节点并将它们添加到队列中。

Implementation / 实现

python

# Solution 2 implementation in Python
from collections import deque

def invertTree(root):
    if root is None:
        return None
    queue = deque([root])
    while queue:
        current = queue.popleft()
        current.left, current.right = current.right, current.left
        if current.left:
            queue.append(current.left)
        if current.right:
            queue.append(current.right)
    return root

Explanation / 解释

  1. Step 1 / 第一步:
  • Check if the root is None. If yes, return None.
    检查根节点是否为空。如果是，返回None。
  1. Step 2 / 第二步:
  • Initialize a queue and add the root to it.
    初始化队列并将根节点添加到队列中。
  1. Step 3 / 第三步:

  • While the queue is not empty, do the following:
    当队列不为空时，执行以下操作：

    • Dequeue the front node.
      将队列前面的节点出队。

    • Swap its left and right children.
      交换其左右子节点。

    • If the left child is not None, add it to the queue.
      如果左子节点不为空，将其添加到队列中。

    • If the right child is not None, add it to the queue.
      如果右子节点不为空，将其添加到队列中。

Complexity Analysis / 复杂度分析

  • Time Complexity: O(n), where n is the number of nodes in the tree.
    时间复杂度: O(n)，其中n是树中的节点数。

  • Space Complexity: O(n), where n is the number of nodes in the tree (due to the queue).
    空间复杂度: O(n)，其中n是树中的节点数（由于队列）。

Key Concept / 关键概念

  • Iterative tree traversal using a queue.
    使用队列的迭代树遍历。

Comparison / 比较

Comparison Between All Approaches

  1. Algorithm:

    • Approach 1 (Recursive Method):

      • Uses recursion to invert the tree.

    • Approach 2 (Iterative Method):

      • Uses a queue to invert the tree iteratively.

  2. Efficiency:

    • Time Complexity:

      • Both approaches have a time complexity of O(n), where n is the number of nodes in the tree.

    • Space Complexity:

      • The recursive method has a space complexity of O(h), where h is the height of the tree.
      • The iterative method has a space complexity of O(n), where n is the number of nodes in the tree.

  3. Readability and Maintainability:

    • Approach 1 (Recursive Method):

      • Clear and concise but uses stack space for recursion.

    • Approach 2 (Iterative Method):

      • Slightly more complex due to the use of a queue, but avoids recursion stack issues.

  4. Best Practice:

    • Recommended Solution: Approach 1 (Recursive Method):
      • Reason: Approach 1 is preferred due to its simplicity and clarity. Although it uses stack space for recursion, it is often easier to understand and implement.

Summary / 总结

  • Use Approach 1 for a simple and clear solution, ensuring readability and maintainability.
  • Approach 1’s recursive nature is straightforward and easy to follow.

Tips / 提示

  • When dealing with binary trees, consider both recursive and iterative approaches for traversal and manipulation.
  • Use helper functions to keep your code organized and readable.

Solution Template for similar questions / 提示

  • Use recursive methods to traverse and manipulate binary trees.
  • Implement iterative approaches for efficiency in certain scenarios.

What does the main algorithm of this question aim to test? / 这个问题的主要算法旨在测试什么？

Understanding of tree traversal techniques, recursion, and iterative methods.

5 more similar questions / 推荐5问题

  1. LeetCode 104. Maximum Depth of Binary Tree
  2. LeetCode 101. Symmetric Tree
  3. LeetCode 100. Same Tree
  4. LeetCode 617. Merge Two Binary Trees
  5. LeetCode 543. Diameter of Binary Tree

Recommended Resources:

LeetCode #226: Invert Binary Tree | FAANG Interview Question by Algo Engine

Invert Binary Tree – Depth First Search – Leetcode 226 by NeetCode

Pre-order Traversal (前序遍历)

In pre-order traversal, we visit the root node first, then recursively visit the left subtree, followed by the right subtree.

Implementation / 实现

python

# Pre-order traversal based inversion
def invertTreePreOrder(root):
    if root is None:
        return None
    # Swap the left and right children
    root.left, root.right = root.right, root.left
    # Recursively invert the left and right subtrees
    invertTreePreOrder(root.left)
    invertTreePreOrder(root.right)
    return root

Explanation / 解释

  1. Step 1 / 第一步:

    • Visit the root node.
      访问根节点。

  2. Step 2 / 第二步:

    • Swap its left and right children.
      交换左右子节点。

  3. Step 3 / 第三步:

    • Recursively invert the left subtree.
      递归翻转左子树。

  4. Step 4 / 第四步:

    • Recursively invert the right subtree.
      递归翻转右子树。

Post-order Traversal (后序遍历)

In post-order traversal, we recursively visit the left subtree first, then the right subtree, and finally the root node.

Implementation / 实现

python

# Post-order traversal based inversion
def invertTreePostOrder(root):
    if root is None:
        return None
    # Recursively invert the left and right subtrees
    invertTreePostOrder(root.left)
    invertTreePostOrder(root.right)
    # Swap the left and right children
    root.left, root.right = root.right, root.left
    return root

Explanation / 解释

  1. Step 1 / 第一步:

    • Recursively invert the left subtree.
      递归翻转左子树。

  2. Step 2 / 第二步:

    • Recursively invert the right subtree.
      递归翻转右子树。

  3. Step 3 / 第三步:

    • Visit the root node.
      访问根节点。

  4. Step 4 / 第四步:

    • Swap its left and right children.
      交换左右子节点。

Difference between Pre-order and Post-order / 前序遍历和后序遍历的区别

Order of Operations / 操作顺序

  • Pre-order (前序遍历):

    • Visit the root node first, then invert the left and right subtrees.
    • 先访问根节点，然后翻转左右子树。

  • Post-order (后序遍历):

    • Invert the left and right subtrees first, then visit the root node.
    • 先翻转左右子树，然后访问根节点。

Tree Modification Timing / 树修改时间

  • Pre-order (前序遍历):

    • The tree is modified (children swapped) as soon as each node is visited.
    • 树在每个节点被访问时立即修改（子节点交换）。

  • Post-order (后序遍历):

    • The tree is modified after both subtrees have been recursively processed.
    • 树在两个子树递归处理后才会被修改。

Which is Better? / 哪个更好？

For inverting a binary tree, both pre-order and post-order traversals are valid and can achieve the same result. However, they differ in the sequence of operations:

  • Pre-order Traversal:

    • Swaps nodes earlier and may be more intuitive since you immediately see the changes as you traverse the tree.
    • 由于您在遍历树时立即看到更改，因此更早交换节点可能更直观。

  • Post-order Traversal:

    • Ensures that subtrees are fully processed before any changes to the parent node. This can sometimes be advantageous in complex tree manipulations but may be less intuitive for this specific task.
    • 确保在对父节点进行任何更改之前完全处理子树。在复杂的树操作中有时可能是有利的，但对于此特定任务可能不太直观。

In practice, pre-order traversal is often preferred for inverting a binary tree due to its simplicity and immediacy of node swapping.

Complexity Analysis / 复杂度分析

Both approaches have the same time and space complexity:

  • Time Complexity: O(n), where n is the number of nodes in the tree.
    时间复杂度: O(n)，其中n是树中的节点数。

  • Space Complexity: O(h), where h is the height of the tree (due to the recursion stack).
    空间复杂度: O(h)，其中h是树的高度（由于递归调用栈）。

Summary / 总结

  • Pre-order Traversal is usually preferred for its simplicity and direct node swapping.
  • Post-order Traversal can be used but involves swapping after processing both subtrees, which can be less intuitive.

Understanding these traversal methods deepens comprehension of tree operations and their practical applications.

Let’s break down the given code step by step with explanations in both English and Chinese to help understand the invertTree method.

Code Breakdown

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root:
            left = root.left
            root.left = self.invertTree(root.right)
            root.right = self.invertTree(left)
        return root

Step 1: Understanding the invertTree Method

English:
The invertTree method is a function that inverts a binary tree. Inverting a binary tree means swapping the left and right children of every node in the tree. This is a common problem in binary tree manipulation.

Chinese:
invertTree 方法是一个用于反转二叉树的函数。反转二叉树意味着交换树中每个节点的左孩子和右孩子。这是二叉树操作中的常见问题。

Step 2: Base Case Check

English:
The method first checks if the root is not None (or a null node). If root is None, the method returns immediately, indicating that there’s nothing to invert. This is the base case of the recursive function.

  • Code: if root:
  • Explanation: If the root exists, the function will proceed to invert the children. If root is None, it returns None.

Chinese:
该方法首先检查 root 是否不是 None（或空节点）。如果 root 是 None，方法会立即返回，表示没有什么可反转的。这是递归函数的基本情况。

  • 代码： if root:
  • 解释： 如果 root 存在，函数将继续反转孩子节点。如果 root 是 None，则返回 None。

Step 3: Storing the Left Child

English:
The method stores the current left child of the root node in a variable left. This is necessary because the next step will overwrite the left child with the inverted right subtree.

  • Code: left = root.left
  • Example: If root.left points to a subtree, it gets stored in left before it is modified.

Chinese:
该方法将 root 节点的当前左孩子存储在变量 left 中。这是必要的，因为下一步将用反转后的右子树覆盖左孩子。

  • 代码： left = root.left
  • 示例： 如果 root.left 指向一棵子树，它将在修改前被存储在 left 中。

Step 4: Recursively Inverting the Right Subtree

English:
The method then recursively inverts the right subtree and assigns it to the left child of the root. This step effectively swaps the left and right subtrees.

  • Code: root.left = self.invertTree(root.right)
  • Explanation: The right subtree is inverted and then placed where the left subtree was, completing the first half of the swap.

Chinese:
接着，该方法递归地反转右子树并将其分配给 root 的左孩子。这一步有效地交换了左子树和右子树。

  • 代码： root.left = self.invertTree(root.right)
  • 解释： 右子树被反转，然后放置在原本左子树的位置，完成了交换的第一部分。

Step 5: Recursively Inverting the Left Subtree

English:
Next, the method recursively inverts the original left subtree (stored in left) and assigns it to the right child of the root. This completes the inversion process.

  • Code: root.right = self.invertTree(left)
  • Explanation: The original left subtree, now stored in left, is inverted and assigned to the right child of root.

Chinese:
接下来，该方法递归地反转原本的左子树（存储在 left 中）并将其分配给 root 的右孩子。这完成了反转过程。

  • 代码： root.right = self.invertTree(left)
  • 解释： 原本的左子树（现在存储在 left 中）被反转并分配给 root 的右孩子。

Step 6: Returning the Root Node

English:
After both left and right subtrees have been inverted, the method returns the root node, which now represents the root of the inverted binary tree.

  • Code: return root
  • Explanation: This ensures that each recursive call returns the root of its respective (sub)tree, ultimately leading to the entire tree being inverted.

Chinese:
在左子树和右子树都被反转之后，该方法返回 root 节点，现在它表示反转后的二叉树的根节点。

  • 代码： return root
  • 解释： 这确保了每个递归调用都返回其各自（子）树的根节点，最终导致整个树被反转。

Full Process Overview

English:
The method works by recursively inverting the left and right children of each node in the tree. The recursion ensures that every subtree is inverted before the node itself is adjusted. The base case prevents further recursion when a leaf node’s children are None.

Chinese:
该方法通过递归地反转树中每个节点的左孩子和右孩子来工作。递归确保每个子树在调整节点本身之前都被反转。基本情况阻止当叶子节点的孩子为 None 时的进一步递归。

Example Walkthrough

Let’s walk through an example to solidify the understanding:

  • Initial Tree: 

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

  • After Inversion: 

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

The invertTree method will successfully transform the initial tree into its mirror image by swapping all the left and right children at every level of the tree.

Post Views: 36
, , , , ,

•

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *