LeetCode Study : 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.

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

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

前提となるクラス：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

自分の解答

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
        return true;
    }
    if (p != null && q != null) {
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    return false;
}

コード理解

別解

class Solution {
  public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (q == null || p == null) return false;
    if (p.val != q.val) return false;
    return isSameTree(p.right, q.right) &&
            isSameTree(p.left, q.left);
  }
}

Time : / Space : Best -> Worst ->

書かないけど、もう１つの別解は総舐め。ただし、舐め方が一工夫あって、Queueを使う。

• pとqがnullじゃないかとかのチェック
• left,rightをそれぞれaddLastする
• removeFirstして内容を比較

Queueじゃないと比較しつつデータを格納していくってのがやりにくいと思う。

あと、自分のコードだと

if (p == null && q == null) {
}
if (p != null && q != null) {
}

としてるけど、これ2つめのやつ

if (q == null || p == null) {

}

にすれば長いリターン（return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);）最後にもってこれたなぁ。 長いリターンは最後に持ってきたくて気持ち悪かったけど、でも思いつかなかったなぁ。。。

今後のための考え方

• 総なめして行く中でなめるための要素が判明していく場合、Queueを使うといいのかも