[LeetCode 101] Symmetric Tree with JAVA

leetcode.com/problems/symmetric-tree/

Symmetric Tree - LeetCode

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

 

Example 1:

Input: root = [1,2,2,3,4,4,3] Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3] Output: false

 

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• -100 <= Node.val <= 100

/**
 * 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) {
        return check(root.left, root.right);
    }
    public static boolean check(TreeNode left, TreeNode right){
        if (left == null && right == null) return true;
        else if (left == null || right == null) return false;
        
        if (left.val == right.val) {
            return check(left.right, right.left) && check(left.left, right.right);
        }
        else return false;
    }
}

 

1. 어려웠던 점:

- 처음 Inorder로 트리 순회를 한 후, 좌 우 배열을 팰린드롬처럼 비교해주면 된다고 생각하였으나, 중간에 null값이 끼어있으면 null값 때문에 index가 알맞게 되지 않기 때문에 알고리즘이 유효하지 않다는 것을 알게 되었다. (ex. [1, 2, 2, 2, null, 2])

 

2. 알게된 점:

- 오랜만에 트리 문제를 풀며, 트리 순회 방식에 대해 다시 공부하였다. (비록 문제에는 안쓰였지만)

 

3. 알고리즘 풀이:

- 재귀적으로 트리의 left, right를 확인하여 결과값을 도출해낸다.

null 처리를 먼저 해주어야 하는데 나중에 val값을 참조할 때, 에러가 되기 때문이다.

좌, 우 모두 null이라면 참이고, 둘 중 하나만 null이라면 거짓이다.

 

null 처리가 끝난 후에는 두 값이 같은 지 확인해준다.

첫 시작은 root였기 때문에 root의 left,right를 비교해주지만,

그 다음 비교값은 left의 right 와 right 의 left, left의 left와 right의 right이 된다.