【LeetCode】226. Invert Binary Treeを解く

問題へのリンク

問題概要

与えられた二分木を左右反転する．

例：

入力：

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

出力：

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

考えたこと

再帰的に実装する．

まず，ノードが０個つまりroot = []のときnullを返せばよいことが分かる．

では，root != []のときはどうなるか？例を用いて考えてみる：

１．「根」にあたる④はそのままで良い．

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

２．根から連なっている⑦（root.left）と②（root.right）を交換

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

上記の結果と期待される出力を見比べると，⑦に連なっている⑥と⑨は反転する必要がある．
⑦をrootとみなすとステップ２．と同様に根から連なっている⑥（root.left）と⑨（root.right）を交換すれば良い．

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

②についても同様に操作する．

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

これで期待される出力が得られた．

以上から，

• nullのノードの場合nullを返す
• 上記以外の場合，root.leftとroot.rightを交換

という操作を実装し，再帰的に処理すればよいことが分かる．

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root is None:
            return None
        
        # 注意！
        L = self.invertTree(root.right)
        R = self.invertTree(root.left)
        
        root.left = L
        root.right = R
        return root

注意点

回答のプログラム内にある「# 注意！」の部分が無くなると期待された出力が得られなくなる：

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

これは，

root.left = self.invertTree(root.right)

が実行されたとき，root.leftにはroot.rightを反転したノードで上書きされてしまい，次の処理

root.right = self.invertTree(root.left)

では元のroot.leftが失われているためである．