[Easy] LeetCode- no.101 Symmetric Tree : Java

https://leetcode.com/problems/symmetric-tree/description/?envType=study-plan-v2&envId=top-interview-150

 

 

문제

이진 트리의 루트가 주어졌을 경우, 좌우 대칭인지 여부를 판단할 것

좌 : true 우 : false

 

 

 

풀이

참고

LeetCode 101(Symmetric Tree, java)

    public boolean isSymmetric(TreeNode root) {
        return checkSymmetric(root.left, root.right);
    }

    private boolean checkSymmetric(TreeNode leftNode, TreeNode rightNode) {
        if (leftNode == null && rightNode == null) {
            return true;
        }

        if (leftNode == null || rightNode == null) {
            return false;
        }

        if (leftNode.val != rightNode.val) {
            return false;
        }

        return checkSymmetric(leftNode.left, rightNode.right) && checkSymmetric(leftNode.right, rightNode.left);
    }

• 처음 했던 고민 : 좌우를 비교해야 하는데, isSymmetric은 파라미터를 하나만 받으니 이 함수로 재귀 호출은 안 될 것 같음
• 블로그 참고 후 해결 : 새 함수를 작성하면 된다 ㅎㅅㅎ...
• checkSymmetric()
  • leftNode와 rightNode가 모두 null일 경우, 동시에 끝에 닿았다는 뜻이므로 true 반환
  • leftNode와 rightNode 둘 중 하나만 null일 경우, false 반환
  • leftNode.val과 rightNode.val이 다르다면 false 반환
  • 좌우 대칭을 비교해야 하는 것이기 때문에 leftNode의 left와 rightNode의 right, leftNode의 right와 rightNode의 left를 checkSymmetric()의 파라미터로 재귀 호출
• 시간복잡도 : O(N)