102. Binary Tree Level Order Traversal

Medium

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Plain Text
복사

Example 2:

Input: root = [1]
Output: [[1]]
Plain Text
복사

Example 3:

Input: root = []
Output: []
Plain Text
복사

Constraints:

•

The number of nodes in the tree is in the range [0, 2000].

•

1000 <= Node.val <= 1000

My solution

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
JavaScript
복사

같은 레벨의 노드들은 배열 안에 모아둔다.

레벨 오더 방식은 이미 구현해봤는데 반복문이라서 재귀로 아래와 같이 구현했다.

const lvOrder = (function () {
  let count = 0;
  let answer = [];

  function lvOrderTraverse(focusNode, k) {
    if (focusNode != null) {
      console.log(count === k, '#', focusNode.val);
      lvOrderTraverse(focusNode.left, k);
      lvOrderTraverse(focusNode.right, k);
    }
  }

  return function (root, k) {
    count = 0;
    answer = [];
    lvOrderTraverse(root);
    return answer;
  };
})();
JavaScript
복사

(i.e., from left to right, level by level).

class Tree {
  constructor() {
      this.root = null
      this.levelSort = []
  }
  levelTravers = (currentNode, level) => {
    if (currentNode === null) return
    if (this.levelSort[level] === undefined || level === 0) this.levelSort.push([])
    if (typeof currentNode.val === 'number') {
      this.levelSort[level].push(currentNode.val)
      this.levelTravers(currentNode.left, level + 1)
      this.levelTravers(currentNode.right, level + 1)
      return
    }
  }
}

const levelOrder = (root) => {
  const myTree = new Tree()
  myTree.root = root
  myTree.levelTravers(myTree.root, 0)
  return myTree.levelSort
}
JavaScript
복사

그냥 리트코드에서 작성을 했다.

갑자기 뜬금없는 값들이 나온다. 입력이랑 관련없는 값인 걸 보니 함수가 계속 그대로 존재해서 그 변수가 덮어씌워진 것 같다. 자유변수 answer를 사용할 때마다 새로 초기화해줘야겠다고 생각해서 19번라인을 추가했다.

콘솔한개를 지우니 괜찮은 성능이 나왔다.

좀 아쉬운 부분이 배열이었는지 보고 2가지로 나눠서 만들어주는 부분인데 이게 배열인지 아닌지 확인하지 않고도 할 수 있다면 좀더 개선되지 않을까 싶다.

const lvOrder = (function () {
  let answer = [];
  function levelOrderTraverse(focusNode, L) {
    if (focusNode != null) {
      if (Array.isArray(answer[L])) {
        answer[L].push(focusNode.val);
      } else {
        answer[L] = [focusNode.val];
      }
JavaScript
복사

아무리 봐도 이상해서 push를 일단 없애보려고 노력했다. 왜냐하면 push는 원본배열을 수정해버리는 mutator method이므로 함수형 프로그래밍에서 지양해야했기 때문에 스프레드연산자로 해결할 수 있는 방식이 떠올라 아래와 같이 바꾸었더니 좋은 성능이 나왔다. 97%보다 빠른 걸 보니 놀라웠다.

answer[L] =answer[L]? [...answer[L], focusNode.val]:[focusNode.val];
JavaScript
복사

앞의 answer[L]이 배열로 존재하지 않는 경우 접근했을 때 undefined가 나오기 때문에 이 경우에는 배열에 val를 그대로 넣어서 할당하고 만약 이미 배열로 존재하면 스프레드연산자로 push를 대체했다.

다시 한번 리팩토링한 덕분에 엄청난 성능 향상을 얻을 수 있었다. 앞으로도 이런 연습을 많이 해서 자연스럽게 할 수 있도록 해야겠다. ㄷ

소스코드

const lvOrder = (function () {
  let answer = [];
  function levelOrderTraverse(focusNode, L) {
    if (focusNode != null) {
      answer[L] = answer[L] ? [...answer[L], focusNode.val] : [focusNode.val];
      levelOrderTraverse(focusNode.left, L + 1);
      levelOrderTraverse(focusNode.right, L + 1);
    }
  }
  return (node, L) => {
    answer = [];
    levelOrderTraverse(node, L);
    return answer;
  };
})();

/**
 * 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 {number[][]}
 */
const levelOrder = function (root) {
  return lvOrder(root, 0);
};
JavaScript
복사