LeetCode 101 - Symmetric Tree (Easy)

문제

LeetCode - 101번

풀이 과정

주어진 트리가 최상위 루트를 중심으로 서로 대칭구조를 이루고 있는지 판단하는 문제입니다.

이를 위해서 대칭구조를 가지고 있는 트리를 하나 예시로 그려서 알고리즘을 설계하였습니다.

위와 같이 대칭 구조를 가지고 있는 트리를 어떤 방법으로 판단해줄 수 있을까요?

여러가지 방법이 있겠지만 저는 트리의 순회를 응용하여 구현하였습니다.

대칭적인 구조를 가진 트리는 최상위 루트를 기준으로 왼쪽 서브트리와 오른쪽 서브트리의 배치가 서로 반대이기 때문에
왼쪽 서브트리에서는 일반적인 전위 순회 를 수행하였고, 오른쪽 서브트리에서는 대칭되어 있다는 가정하에
왼쪽 자식보다 오른쪽 자식을 먼저 방문하게하여 탐색을 수행했습니다.

만약 해당 트리가 대칭구조를 가지고 있다면 두 순회 결과가 동일해야하므로 이를 활용해 트리의 대칭 유무를 판단할 수 있습니다.

실제 구현에서는 각각의 순회를 별도의 함수로 구현한 것이 아닌 mode 를 인자로 주어
왼쪽과 오른쪽 서브트리에 대해 탐색 순서를 결정하도록 하였습니다.

코드

/**
 * 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)
 * }
 */

function traversal_with_mode(root, visit, mode) {
  if (root === null) {
    visit.push(null);
    return;
  }

  visit.push(root.val);
  if (mode === "left") {
    traversal_with_mode(root.left, visit, mode);
    traversal_with_mode(root.right, visit, mode);
  } else {
    traversal_with_mode(root.right, visit, mode);
    traversal_with_mode(root.left, visit, mode);
  }
}

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
  let left_trace = [];
  let right_trace = [];

  traversal_with_mode(root, left_trace, "left");
  traversal_with_mode(root, right_trace, "right");

  // 두 방문 결과를 비교한다.
  if (left_trace.length !== right_trace.length) {
    return false;
  } else {
    for (let i = 0; i < left_trace.length; i++) {
      if (left_trace[i] !== right_trace[i]) {
        return false;
      }
    }
  }

  return true;
};