[알고리즘] #Increasing Order Search Tree

출처: https://leetcode.com/problems/increasing-order-search-tree/

Increasing Order Search Tree - LeetCode

 

문제

Given a tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.

 

 

Note:

1. The number of nodes in the given tree will be between 1 and 100.
2. Each node will have a unique integer value from 0 to 1000.

 

 

---

풀이(Javascript)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
function inorder(node, arr) {
    // 노드가 undefined 이거나 노드에 값이 없을 때 종료
    if(node == undefined || node.val == null) {
        return;
    }
    
    // 왼쪽 자식노드가 현재 노드보다 값이 작기 때문에 먼저 inorder 메서드를 실행한다.
    if(node.left) {
        inorder(node.left, arr);    
    }
    
    // 현재 노드 값 추가 
    arr.push(node.val);
    
    // 오른쪽 자식노드가 현재 노드보다 값이 크기 때문에 나중에 inorder 메서드를 실행한다.
    if(node.right) {
        inorder(node.right, arr);
    }    
    
    return arr;
    
}

var increasingBST = function(root) {
    
    var arr = [];
    // 중위순회
    inorder(root, arr);
    
    var newRoot = new TreeNode(0);
    var curNode = newRoot;
        
    for(var i=0; i<arr.length; i++) {
        curNode.right = new TreeNode(arr[i]);
        curNode = curNode.right;
    }
    
    return newRoot.right;
};

 

이진트리를 중위순회하면 보통 오름차순으로 정렬되어서 나온다. 만약에 노드의 값을 배열이나 리스트로 받았다면 바로 정렬한 뒤에 중간에 null을 넣어서 리턴했을 거다. 하지만 실제 문제 풀이할 때에는 TreeNode 객체에 담겨 있다고 가정하기 때문에, 순회하면서 리스트에 값을 넣어 준 뒤 새로운 TreeNode에 오른쪽 자식노드로 계속 추가해주어야 한다.