Leetcode # 226. Invert Binary Tree

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

Solution

示例

Ａ
ＢＣ
ＤＥ　ＦＧ
ＨＩＪＫＬＭＮＯ

Ａ
ＣＢ
➡︎ＦＧＤＥ
ＬＭＮＯＨＩＪＫ

Ａ
ＣＢ
➡︎ＧＦＥＤ
ＮＯＬＭＪＫＨＩ

Ａ
ＣＢ
➡︎ＧＦＥＤ
ＯＮＭＬＫＪＩＨ

證明：Mathematical Induction 數學歸納法

Swap all left child and right child of every node from root level to last level, you can get inverted binary tree.

\begin{align}
& N_{i, j} \text{ is } j^\text{th} \text{ node in level } i, i \text{start from 0}, j \in [0, 2^i) \\
& N_{i, j’} := N_{i, (2^i – 1 – j)} \text{ is the mirrored } N_i, j \\
\\
& \text{Base Case: } \\
& \quad \text{If you swap the left child and the right child of root, }\\
& \quad \text{Level_1 was inverted. } \\
& \quad \text{The statement holds for the first node root, you inverted from root to } \text{level}_1 \\
\\
& \text{Induction step: } \\
& \quad \text{Assume the tree form root to } \text{level}_i \text{ are inverted. } \\
& \quad \text{The origin position of } P_{i, j} \text{ is }j \text{. } \\
& \quad \text{For now, the new position of } P_{i, j} \text{‘s parent } P_{(i – 1), (j \ // \ 2)} \text{ is } (2^{i-1} – 1 – (j \ // \ 2)) \text{.} \\
& \quad \text{The current position of } P_{i, j} \text{ is } \\
& \qquad 2[2^{i-1} – 1 – (j \ // \ 2)] +  
\begin{cases}
0 \text{, if } P_{i, j} \text{ was right child. } \\
1 \text{, if } P_{i, j} \text{ was left child. } 
\end{cases}\\
& \qquad = \left[2^i – 2 – \left(j – 
\begin{cases}
1 \text{, if } P_{i, j} \text{ was right child. } \\
0 \text{, if } P_{i, j} \text{ was left child. } 
\end{cases}
\right) \right] + \begin{cases}
0 \text{, if } P_{i, j} \text{ was right child. } \\
1 \text{, if } P_{i, j} \text{ was left child. } 
\end{cases}\\
& \qquad = (2^i – 2 – j + 1) = (2^i – 1 – j) = N_{i, j’} \\
& \quad \text{We showed for every } i \text{, if the statement holds for level } i \text{, then it holds for level }(i + 1) \\
\end{align}

Complexity and Codes

Time Complexity: O(len(tree))
Space Complexity: O(len(tree))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    queue = collections.deque([root]) if root else None

    while queue:
      cur = queue.pop()
      if cur.left:  queue.append(cur.left)
      if cur.right: queue.append(cur.right)
      cur.left, cur.right = cur.right, cur.left

    return root

Last Updated on 2023/08/16 by A1go