LeetCode Study : 101. Symmetric Tree

問題

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

Example 1:

    1
   / \
  2   2
 / \ / \
3  4 4  3

Example 2:

    1
   / \
  2   2
   \   \
   3    3

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

自分の解答

public boolean isSymmetric(TreeNode root) {
    if (root == null) {
        return true;
    }
    reverseTree(root.left);
    return isSameTree(root.left, root.right);
}

private void reverseTree(TreeNode node) {
    if (node == null) {
        return;
    }
    TreeNode temp = node.left;
    node.left = node.right;
    node.right = temp;
    reverseTree(node.left);
    reverseTree(node.right);
}

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

コード理解

別解

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

public boolean isMirror(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return true;
    if (t1 == null || t2 == null) return false;
    return (t1.val == t2.val)
        && isMirror(t1.right, t2.left)
        && isMirror(t1.left, t2.right);
}

Time : / Space :

これはやられましたね。綺麗です、別解。たしかに、右と左、左と右をどんどん見ていけばいいのか。思いつかなかった。そして理解した。

自分のも意味はわかりやすくていいと思うんだけど。でもまぁ無駄すぎる。細かく言えば別解はTime complexity だけど、自分のはになっちゃってる。

今後のための考え方

• TreeがMirrorになっているかどうかは right<->left, left<->rightを比較すればよろしい。