🖋
LeetCode 226. Invert Binary Tree
はじめに
LeetCode 「226. Invert Binary Tree」の問題をGoで解きました。
問題
問題文
Given the root of a binary tree, invert the tree, and return its root.
和訳
二分木のルートが与えられたら、木を反転させ、そのルートを返す。
例
1 1
/ \ / \
2 7 → 7 2
/ \ / \ / \ / \
1 3 6 9 9 6 3 1
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
2 1
/ \ → / \
1 3 3 1
Input: root = [2,1,3]
Output: [2,3,1]
Input: root = []
Output: []
制約
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
解答:DFS（深さ優先、再帰）
二分木を反転させる問題です。
全てのノードで左右の子ノードを入れ替えるために、木全体を一度走査する必要があります。
再帰（DFS）を使えば、 今いるノードで左右を入れ替え→左右の子ノードに対して同じ操作を繰り返す。 という形で自然にかけます。
例1だとrootの左右の子ノードをを入れ替えると以下となります。
1
/ \
7 2
/ \ / \
6 9 1 3
そして、7 と 2の左右の子ノードを入れ替えると以下となります。
1
/ \
7 2
/ \ / \
9 6 3 1
コード
func invertTree(root *TreeNode) *TreeNode {
if root != nil {
// 左右の子ノードを入れ替える
root.Left, root.Right = root.Right, root.Left
// 左右のサブツリーを反転
invertTree(root.Left)
invertTree(root.Right)
}
// 反転後のrootを返す
return root
}
各ノードで左右の入れ替えだけやればいいので、呼び出し元で戻り値を受け取る必要もなく、最終的にrootを返す形となります。
最後に全ての再帰が終了した時に、最初に呼ばれたinvertTree(root) の呼び出しが root を return します。
計算量
- 時間的計算量：O(n)
- n はノード数（各ノードを1回ずつ訪れる）
- 空間的計算量：O(h)
- h は木の高さ（再帰呼び出しのスタックが木の高さ分使われる）
参考
二分木の問題は、以下の記事でも紹介していますので、参考にしてください。
Discussion