LeetCode 101.Symmetric Tree

LeetCode 101.Symmetric Tree

leetcode.com

自分のアプローチ

• ２つのサブノードを比較していく
• 以下の条件を満たす場合は、symmetric と判定
  1. サブノードの root の値が等しい
  2. 左のサブノードの左の子ノードと右のサブノードの右の子ノード (外外)
  3. 右のサブノードの右の子ノードと右のサブノードの左の子ノード (内内)

自分のアプローチと解答例の差異

• まず解答例では base case でサブツリーの root で比較している。
• サブツリーの子ノードで判定すると 16 通りになりそれだけでも混乱する原因になる。
• 起点となるhelper関数の引数の渡し方も解答例ではサブツリーのrootをそれぞれ渡しており、自分のアプローチではhelper関数を呼ぶ時点で条件分岐して煩雑になっている。
• 解答例のように、ただツリーのrootを重複する形で渡してもうまくいく

解答例のアプローチ

• base case は次の条件（1. || 2.）

  1. 両方とも null なら symmetric
  2. どちらかひとつ null なら asymmetric
  3. 両方とも null でなければ recursive case へ

• recursive case では自分のアプローチと同じ条件を再帰的に課している（1.&& 2. && 3.）

  1. サブノードの root の値が等しい
  2. 左のサブノードの左の子ノードと右のサブノードの右の子ノード (外外)
  3. 右のサブノードの右の子ノードと右のサブノードの左の子ノード (内々)

symmetricな構造

asymmetricな構造

どうしたら解けたか

• 実際にsymmetricとasymmetricの構造（深さ固定）を紙に数パターン書きだすと解答例のようなアプローチが見えてきたかも
• ツリーの形とノードの値を分けてパターンを探したほうがよかった

解答例

public boolean isSymmetric(TreeNode root) {
  return isSymmetricHelper(root, root);
}

private boolean isSymmetricHelper(TreeNode lRoot, TreeNode rRoot) {
   if (lRoot == null && rRoot == null) return true;    //symmetricな構造
   if (lRoot == null || rRoot == null) return false;   //asymmetricな構造
   return (lRoot.val == rRoot.val)
       && isSymmetricHelper(lRoot.right, rRoot.left)
       && isSymmetricHelper(rRoot.left, lRoot.right);
}

自分の解法 (受かっていない)

public boolean isSymmetric(TreeNode root) {

    if (root == null) return true;
    if (root.left == null && root.right == null) return true;
    if (root.left != null && root.right != null) return isSymmetricHelper(root.left,
 root.right);
    return false;
  }

  private boolean isSymmetricHelper(TreeNode lRoot, TreeNode rRoot) {
    // base case
    if (lRoot.left == null && lRoot.right == null && rRoot.left == null && rRoot.right == null)
    {
      return lRoot.val == rRoot.val;
    }

    // recursive case
    if (lRoot.val == rRoot.val) {

      if ((lRoot.left == null && rRoot.left == null && lRoot.right == null && rRoot.right == null))
        return false;

      return isSymmetricHelper(lRoot.left, rRoot.right)
          && isSymmetricHelper(lRoot.right, rRoot.left);

    } else {
      return false;
    }
  }