Symmetric Tree

---

💬 문제

[문제 링크]

이진 트리의 시작점 노드 root
트리가 root의 자식 기준으로 좌우 반전된 상태인지 판단

✍️ 나의 풀이

/**
 * @param {TreeNode} root
 * @return {boolean}
 */

var dfs = function(left, right) {
    if (left === null && right === null)
        return true;
    if (left === null || right === null || left.val !== right.val)
        return false;
    let leftCheck = dfs(left.left, right.right);
    let rightCheck = dfs(left.right, right.left);
    return leftCheck && rightCheck;
};

var isSymmetric = function(root) {
    return dfs(root.left, root.right);
};

root의 왼쪽 자식, 오른쪽 자식 즉 두번째 depth부터 재귀함수로 반복 확인함
왼편을 기준으로 하여, 왼편은 왼쪽 자식으로 오른편은 오른쪽 자식으로 넘어가는 것을 leftCheck
반대의 경우를 rightCheck로 하여 둘 다 true일 때 (이하 노드의 대칭 값이 같을 때) true 반환

📌 결과

Accepted
Runtime 58ms (Beats 71.38%)
Memory 51.60MB (Beats 53.47%)

📚 러닝 포인트

이번에도 모든 노드를 확인해야 하기 때문에, 두 방법을 모두 사용할 수 있었지만 DFS를 선택했다. (저번에 DFS가 좀 더 빠르다는 것을 알았으므로) 두 노드의 값을 비교해야 하므로 두 개의 포인터가 필요한데, 구현해야하는 함수는 매개변수가 하나여서 별도의 재귀함수를 만들었다. 어렵지 않게 구현해서 이번에도 BFS 방식에 도전해봤다.

var isSymmetric = function(root) {
    let leftQueue = [root.left];
    let rightQueue = [root.right];

    while (leftQueue.length) {
        let leftNode = leftQueue.shift();
        let rightNode = rightQueue.shift();
        
        if (leftNode === null && rightNode === null)
            continue ;
        if (leftNode === null || rightNode === null || leftNode.val !== rightNode.val)
            return false;
        
        leftQueue.push(leftNode.left);
        rightQueue.push(rightNode.right);
        leftQueue.push(leftNode.right);
        rightQueue.push(rightNode.left);
    }

    return leftQueue.length === rightQueue.length;
};

노드 비교용 조건문은 동일하고, 유의해야할 점은 자식 노드가 없어도 queue에 저장하지 않고 넘어가는 것이 아니라 null 값이라도 저장해두어야 한다는 것이다. 순서가 꼬여서 서로 다른 위치의 노드를 비교할 수 있기 때문이다. 또 테스트 조건이 달라서 그랬겠지만 돌려보니 런타임 51ms가 나온다(...)