[LeetCode][JS]Increasing Order Search Tree

문제

문제: https://leetcode.com/problems/increasing-order-search-tree/

위 그림처럼 tree모양을 오른쪽으로만 뻗게 만들어라.

해결방법

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

위의 하나하나의 노드들은 각각 TreeNode의 객체로 linked돼 있다.

내가 먼저 해결했던 방법의 로직이다.

1. 모든 노드를 돌면서 각 value를 수집한다.
2. value를 정렬한다.
3. NodeTreeArr: 정렬된 value를 TreeNode형태로 매핑한다.
4. NodeTreeArr의 마지막 인덱스 -1 에서부터 0까지 돌면서 right에 뒤에 있는 값을 넣는다.

조금 뒤에 다시 다루겠지만 value를 정렬하고, nodeTreeArr의 마지막 인덱스-1 부터 순회하는 것도 뭔가 이상했다.

code

var increasingBST = function (root) {
  const nodeValue = [];
  //순회하며 nodeValue에 value를 저장하는 함수
  const dfs = (node) => {
    if (!node) return;
    nodeValue.push(node.val);
    dfs(node.left);
    dfs(node.right);
  };
  dfs(root);
  // value를 정렬한다.
  nodeValue.sort((a, b) => a - b);
  // value를 각각 TreeNode객체로 만든다
  const nodeTreeArr = nodeValue.map((val) => new TreeNode(val, null, null));
  // 뒤의 값을 앞에값에 right로 넣는 방식으로 해결했다.
  for (let i = nodeTreeArr.length - 2; i >= 0; i--) {
    nodeTreeArr[i].right = nodeTreeArr[i + 1];
  }
  return nodeTreeArr[0];
};

수정사항

위의 코드가 매우 좋지 않은 코드라는 것이 직감적으로 느껴지기 때문에 leetcode의 다른 답안을 보았다. 2개의 중요한 것을 수정할 수 있었다.

1. 노드트리 순회

위의 코드로 해결해도 값은 나온다. 하지만 그래프를 자세히 보면 일정한 특징이 있다.
가장 왼쪽으로 깊게 들어간 뒤, 나오면서 번호가 매겨진다.
즉, 트리 순회의 중위 순회로 돌면 번호 순서대로 value를 얻을 수 있다.

중위 순회란?
left -> root -> right 순으로 트리를 순회하는 것
위 그림에서 2->3->4 로 순회하는 모양이 left->root->right 이런식이다.

즉, 코드에서는 dfs로 맨 왼쪽으로 쭉들어가서 종료되고 튀어나올 때 push해주면 된다.

const dfs = (node) => {
  if (!node) return;
  else {
    dfs(node.left);
    nodeValue.push(node.val);
    dfs(node.right);
  }
};

2. 출력방식

나는 뒤에있는 값을 right에 넣으면서 했지만 for문에서도 한번에 이해하기 힘든 그런 코드가 됐다.
시작을 const treeNode = TreeNode(0)으로 하고 이 객체.right에 계속 추가한다.
출력할 때만 treeNode.right하면 됐었다.
treeNode는 건드리지 않고 currentNode로 treeNode안에서 계속 움직이면서 저장하면 된다.

이렇게 2개의 수정사항을 거친뒤에는 보다 깔끔한 코드가 나오게된다.

code

var increasingBST = function (root) {
  const nodeValue = [];
	
  //중위 순회로 돌면서 value값을 저장한다. sort할 필요X
  const dfs = (node) => {
    if (!node) return;
    dfs(node.left);
    nodeValue.push(node.val);
    dfs(node.right);
  };
  dfs(root);

  const treeNode = new TreeNode(0);
  let currentNode = treeNode;

  //새로운 TreeNode객체를 currentNode.right에 추가해준다.
  for (let x of nodeValue) {
    currentNode.right = new TreeNode(x, null, null);
    currentNode = currentNode.right;
  }

  return treeNode.right;
};