Zenn
🖋

LeetCode 101. Symmetric Tree

に公開
Go
LeetCode
tech

はじめに

LeetCode 「101. Symmetric Tree」の問題をGoで解きました。

問題

https://leetcode.com/problems/symmetric-tree/description/

問題文

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

和訳
二分木のrootが与えられたら、それがそれ自身の鏡（すなわち、その中心を中心に対称）であるかどうかをチェックする。

例

         1          
      /     \        
     2       2    
   /  \     /  \    
  3    4   4    3    

Input: root = [1,2,2,3,4,4,3]
Output: true

         1          
      /     \        
     2       2    
      \        \    
       3        3    

Input: root = [1,2,2,null,3,null,3]
Output: false

制約

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

解答1:DFS（深さ優先検索・再帰）

二分木が左右対称かを判定する問題です。
左右の２つのノードの対称性をチェックします。

isMirror関数では、2つのノードpとqに対して、以下をチェックします。

  • 両者がnil: true
  • 片方だけnil: false
  • 値が違う: false
  • 再帰的に p.Left と q.Right, p.Right と q.Left が鏡になっているかをチェック

全体のルートに対して、上記をチェックします。

コード

func isSymmetric(root *TreeNode) bool {
    return isMirror(root.Left, root.Right)
}

func isMirror(p, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }

    if p == nil || q == nil {
        return false
    }

    if p.Val != q.Val {
        return false
    }

    return isMirror(p.Left, q.Right) && isMirror(p.Right, q.Left)
}

計算量

  • 時間的計算量：O(n)
    • n はノード数（各ノードを1回ずつ訪れる）
  • 空間的計算量：O(h)
    • h は木の高さ（再帰呼び出しのスタックが木の高さ分使われる）

解答2：BFS（幅優先探索、Queue使用）

解答1では再帰的に深さ優先で木を探索しましたが、キューを使った幅優先探索でも同様に対称性をチェックできます。
ポイントは、左右対称かどうか をノードのペアを使って都度チェックする点です。

1回目のループで queue = [2, 2] → 値は等しいので次へ
2回目: queue = [3, 3, 4, 4] → 両ペアとも値が等しい → 次へ
...
といったように、各ペアを取り出して比較していくイメージです。

コード

func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }

    queue := []*TreeNode{root.Left, root.Right}

    for len(queue) > 0 {
        p := queue[0]
        q := queue[1]
        queue = queue[2:]

        if p == nil && q == nil {
            continue
        }

        if p == nil || q == nil {
            return false
        }

        if p.Val != q.Val {
            return false
        }

        // 鏡の順番で追加
        queue = append(queue, p.Left, q.Right)
        queue = append(queue, p.Right, q.Left)
    }

    return true
}

計算量

  • 時間的計算量：O(n)
    • n はノード数（各ノードを1回ずつ訪れる）
  • 空間的計算量：O(w)
    • w は木の最大幅（Queue に最大で一度に保持するノード数）

参考

二分木の問題は、以下の記事でも紹介していますので、参考にしてください。

GitHubで編集を提案

Discussion