[LeetCode] Increasing Order Search Tree

이진트리의 root 노드가 주어질 때 트리를 in-order로 정렬해서 가장 왼쪽에 있는 노드가 root가 되고 왼쪽 자식이 없이 오른쪽 자식만 있는 트리로 만들어야 하는 문제이다

Example을 보자

예시 1번을 보면 가장 왼쪽에 있는 노드인 1이 새로운 root노드가 되고

in-order 순서대로 오른쪽 자식으로 이루어져 있는 트리를 만들면 된다

const increasingBST = function(root) {
    let nodeArr = [];
    helper(root, nodeArr);
    const newRoot = new TreeNode(nodeArr[0]);
    let currentNode = newRoot;
    for(let i = 1; i < nodeArr.length; i++) {
        const createNode = new TreeNode(nodeArr[i]);
        currentNode.right = createNode;
        currentNode = createNode;
    }
    
    return newRoot
};

const helper = (node , arr) => {
        if(node) {
            helper(node.left, arr);
            arr.push(node.val);
            helper(node.right, arr);
        }else {
            return null;
        }
}

먼저 각 노드들을 in-order로 순회를 해서 배열에 저장한다음 새로운 트리를 만들어주려고 했다

helper 함수를 하나 만들어서 in-order 순서로 nodeArr에 node를 넣어주었다

그 다음 새로운 루트노드가 되는것은 nodeArr[0]이므로 newRoot를 만들어 주고

currentNode 라는 변수에 newRoot를 할당해주었다

그 다음 배열을 반복문을 돌면서 현재 배열의 값을 val로 가지는 새로운 노드를 만들고 currentNode의 오른쪽 자식으로 연결시켜주었다

그 다음 currentNode를 createNode로 바꿔주었다

submit을 해보니

정답이었다!