[JAVA] LeetCode 101 - Symmetric Tree

Given a binary tree, check whether it is a mirror of itself

(ie, symmetric around its center).

 

이진 트리가 주어질 때, 대칭 되는지 확인하여라.

(가운데를 중심으로)

 

 

 

풀이 방법

트리가 대칭이 되기 위한 조건들을 뽑아보자.

그림을 그려보면 아래 코드를 이해하기 더 쉬울 것!

 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) 
            return true;
        
        return isSymmetric(root.left, root.right);
    }
    
    public boolean isSymmetric(TreeNode left, TreeNode right) {
    	// left right 노드가 모두 null이면 대칭
        // 둘 중 하나만 null일 경우는 비대칭
        if(left == null && right == null) return true;
        else if(left != null && right == null) return false;
        else if(left == null && right != null) return false;
        
        // left right 노드의 값이 다를 경우 비대칭
        // left -> left 노드와 right -> right 노드가 다를 경우 비대칭
        // left -> right 노드와 right -> left 노드가 다를 경우 비대칭
        // 이 외는 대칭
        if(left.val != right.val) return false;
        if(!isSymmetric(left.left, right.right)) return false;
        if(!isSymmetric(left.right, right.left)) return false;
        
        return true;
    }
}