[LeetCode] 101. Symmetric Tree

leetcode.com/problems/symmetric-tree/

Symmetric Tree - LeetCode

 

핵심 아이디어

tree를 순회하되, 좌우가 대칭인 트리인지 검증하는 프로그램을 짜야한다.

분명 쉬워보였는데 구현할 방법이 정확하게 떠오르지 않아서 풀이를 보았다.

풀이에서는 바깥쪽 트리들을 먼저 비교하고 점차 안쪽의 트리들을 비교하는 방법을 택했다.

즉,

트리를 2개(a,b)씩 비교하되,

a의 left, b의 right

a의 right, b의 left

순으로 큐에 넣어서 대칭인지 검사하는것이다.

 

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    const q = [root, root];
    while(q.length > 0){
        const [node1, node2] = [q.shift(), q.shift()];
        if(node1 === null && node2 === null) continue;
        if(node1 === null || node2 === null) return false;
        if(node1.val !== node2.val) return false;
        
        q.push(node1.left);
        q.push(node2.right);
        q.push(node1.right);
        q.push(node2.left);
    }
    return true;
};