[LeetCode] Flip Equivalent Binary Trees

Flip Equivalent

처음 코드

class Solution {
        public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return true;

        if (root1.val != root2.val || root1.left.val != root2.left.val && root1.left.val != root2.right.val || root1.right != root2.left.val && root1.right.val != root2.right.val)
            return false;

        boolean equiv1, equiv2;

        if (root1.left.val == root2.left.val) {
            equiv1 = flipEquiv(root1.left, root2.left);
            equiv2 = flipEquiv(root1.right, root2.right);
        }
        else if (root1.left.val == root2.right.val) {
            equiv1 = flipEquiv(root1.left, root2.right);
            equiv2 = flipEquiv(root1.right, root2.left);
}

if (equiv1 && equiv2) return true;
else return false;
        }
}

노드가 null일 때는 val값을 계산할 수 없다. 널 포인터 어쩌고 에러 발생한다는 걸 간과했다..^-^..

수정한 코드

class Solution {
        public boolean flipEquiv(TreeNode root1, TreeNode root2) {

        if (root1 == null && root2 == null) return true;

        root1 = (root1 == null) ? new TreeNode(-1) : root1;
        root2 = (root2 == null) ? new TreeNode(-1) : root2;
        int left1 = (root1.left == null) ? -1 : root1.left.val;
        int right1 = (root1.right == null) ? -1 : root1.right.val;
        int left2 = (root2.left == null) ? -1 : root2.left.val;
        int right2 = (root2.right == null) ? -1 : root2.right.val;

        if (root1.val != root2.val || left1 != left2 && left1 != right2 || right1 != left2 && right1 != right2)
            return false;

        boolean equiv1 = true, equiv2 = true;

        if (left1 == left2) {
            equiv1 = flipEquiv(root1.left, root2.left);
            equiv2 = flipEquiv(root1.right, root2.right);
        }
        else if (left1 == right2) {
            equiv1 = flipEquiv(root1.left, root2.right);
            equiv2 = flipEquiv(root1.right, root2.left);
        }

        if (equiv1 && equiv2) return true;
        else return false;
        }
}

그래서 현재 노드랑 자식 노드들이 null일 때를 대비해서 따로 변수 만들어서 저장했더니 통과됐다!!
내 코드의 아이디어는 일단 재귀적으로 노드 값이 같은지 확인하는 것이다.

1. 현재 노드가 서로 일치하는지 확인
2. 자식 노드의 값이 모두 같은지 확인
3. subtree 1이랑 subtree 2에서 재귀적으로 함수 호출해서 둘이 모두 true를 리턴하면 최종적으로 true 리턴. (서브트리 중에서 하나라도 Flip할 수 없는 게 발견된다면 전체 트리가 flip할 수 없는 거니까!)

• 솔루션 보니까 null인 경우 어쩌고 따지지 말고.. 간단하게 써도 될 듯...