Zenn
🖋

LeetCode 100. Same Tree

に公開
Go
LeetCode
tech

はじめに

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

問題

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

問題文

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

和訳
2つの2分木pとqの根が与えられたとき、それらが同じかどうかをチェックする関数を書きなさい。

2つの2分木は、構造的に同じで、ノードの値が同じであれば同じとみなされる。

例

         1                1       
      /     \          /     \    
     2       3        2       3   

Input: p = [1,2,3], q = [1,2,3]
Output: true

         1                1       
      /                     \    
     2                       2  

Input: p = [1,2], q = [1,null,2]
Output: false

         1                1       
      /     \          /     \    
     2       1        1       2   

Input: p = [1,2,1], q = [1,1,2]
Output: false

制約

  • The number of nodes in both trees is in the range [0, 100].
  • -104 <= Node.val <= 104

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

pとqが同じ二分木と言えるかを判定する問題です。
典型的な 木構造の再帰的走査パターン になります。
各ノードに対して、左右の子ノードが一致するか を再起的に確認していきます。

なお、BFSでも解けると思いますが、Queueにnilを入れる必要が出たり、左右のノードをペアでQueueに入れて順序よく比較する必要があります。
そのため、実装がやや複雑になります。
再帰（DFS）で書いた方がシンプルに実装することができます。

コード

func isSameTree(p *TreeNode, 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 isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

計算量

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

参考

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

GitHubで編集を提案

Discussion