# LeetCode Easy 100. Same Tree

tags: leetcode

問題

• Explore
• Problems

2つの二分木を与えられた時に, それらが同じかどうかを調べる関数を書け

2つの二分木は構造的に同じでノードが同じ値を持っていたら同じとみなされる

解法(recursive)

二分木は再帰的なデータ構造を持つので再帰的に解くことをまずは考えます

以下, 同じときはtrue, 違う時はfalseとします

• 基底は両方とも同じ根を持つ時(true)とそれ以外(false)
• では, 再帰的に考えます
• 最初は根を指すポインタが与えられるので, 子のノードに再帰的に進みます
  • 子は右と左があり, これらのどちらかが同じでなければfalseを返します
  • 同じであるときはtrueです
  • つまり, 再帰関数をand演算子で連結すれば良いです

例外として根を持たないときを考えます

片方のみ根を持たないなら当然falseで両方とも持たないならtrueです

計算量

ノードの数を$n$とします

• 空間計算量は再帰関数はノードを遡るだけなので新たに必要なメモリはなく$O(1)$
• 時間計算量は再帰関数をノード数に応じて実行するので$O(n)$

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
      if p == None and q == None:
        return True
      elif p == None or q == None:
        return False
      
      if p.val == q.val:
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
      else:
        return False

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  bool isSameTree(TreeNode* p, TreeNode* q) {
    if (p == NULL && q == NULL) {
      return true;
    } else if (p == NULL || q == NULL) {
      return false;
    }
    if (p->val == q->val) {
      return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    } else {
      return false;
    }
  }
};