LeetCodeに毎日挑戦してみた 100. Same Tree(Python、Go)


Leetcodeとは

leetcode.com
ソフトウェア開発職のコーディング面接の練習といえばこれらしいです。
合計1500問以上のコーデイング問題が投稿されていて、実際の面接でも同じ問題が出されることは多いらしいとのことです。

golang入門+アルゴリズム脳の強化のためにgoとPythonで解いていこうと思います。(Pythonは弱弱だが経験あり)

21問目(問題100)

100. Same Tree

問題内容

Given two binary trees, 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.m nums2.

(日本語訳)

  • 2つの二分木が与えられた場合、それらが同じであるかどうかをチェックする関数を記述します。

2つの二分木は、構造的に同一であり、ノードの値が同じである場合、同じであると見なされます。を*。

***Example 1:*

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

考え方

  1. 最初のvalを比較し、再帰処理で解いていきます。

  2. p==qを満たせばtrue、満たさない場合falseになります

  3. trueならば同一です

  • 解答コード
class Solution(object):
    def isSameTree(self, p, q):
        if p and q:
            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        else:
            return p == q

  • Goでも書いてみます!
func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p != nil && q != nil {
        return p.Val == q.Val && isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
    } else {
        return p == q
    }
}