[LeetCode] - Symmetric Tree

이진 트리가 주어지고 중심을 기준으로 거울처럼 대칭인지 확인

 

sudo code

root 기준 left와 right가 같을 경우 true

left right 양쪽이 null이면 true

left 혹은 right 한쪽이 null이면 false

left left와 right의 right가 같아야 하고

left의 right와 right의 left가 같아야 함

 

1차 시도

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isSame(root.left, root.right);
    }
    public boolean isSame(TreeNode left, TreeNode right) {
        if(left == null && right == null) return true;
        if(left.val != right.val) return false;
        return isSame(left.right, right.left) && isSame(left.left, right.right);
    }
}

java.lang.NullPointerException
  at line 23, Solution.isSame
  at line 24, Solution.isSame
  at line 19, Solution.isSymmetric
  at line 54, __DriverSolution__.__helper__
  at line 84, __Driver__.main
Last executed input:
[1,2,2,null,3,null,3]

2차 시도

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isSame(root.left, root.right);
    }
    public boolean isSame(TreeNode left, TreeNode right) {
        if(left == null && right == null) return true;
        if(left != null && right != null) {
            if (left.val != right.val) return false;
        }else return false; // 둘 중 하나가 null인 경우
        return isSame(left.right, right.left) && isSame(left.left, right.right);
    }
}

Runtime: 0 ms
Memory Usage: 37.4 MB