LeetCode - Minimum Absolute Difference in BST in JavaScript

이번 문제는 아래 트리에서 노드간 절대값 차이가 가장 적은 것을 찾아 반환하는 문제이다. 

위의 트리의 경우 가장 작은 차이는 4 - 3 = 1, 3 - 2 =1, 2 - 1 = 1 등등 1이 반환되어야 한다.

이번에 풀면서 처음으로 트리 순회라는 것에 대해 알게 되었다. 순회 방법은 3가지 (preorder, inorder, postorder) 등이 있다.

 

위 문제의 전략은 트리의 노드를 값의 크기 순으로 정렬을 해준다음, 원소들의 차를 비교하여 가장 크기가 작은 값을 반환하면 된다.

 

인터넷에서 찾은 코드와 내코드를 비교해 보자~~ (자기 공부용)

 

stack over flow 에서 먼저 in order 순회에 대한 것을 찾아 보았다. (아래 참고)

https://stackoverflow.com/questions/38856834/using-javascript-to-code-the-preorder-traversal

using javascript to code the preorder traversal

 

인터넷 참고해서 만든 코드

var getMinimumDifference = function(root) {
    const sortedNode = getSortedNode(root);
    let min;
    
    for (let i = 1; i < sortedNode.length; i++) {
        if (!min) {
            min = Math.abs(sortedNode[0] - sortedNode[i]);
            continue;
        }
        
        const diff = Math.abs(sortedNode[i-1] - sortedNode[i]);
        
        if (min > diff) {
            min = diff;
        }
    }
    
    function getSortedNode(root, acc = []) { 
        if (!root) return;
        if (root.left) getSortedNode(root.left, acc);
        acc.push(root.val); // 여기에 push해야 inorder가 된다.
        if (root.right) getSortedNode(root.right, acc);
        
        return acc;     
    }
    
    return min;
};

 

내코드

var getMinimumDifference = function(root) {
    const sortedNode = getSortedNode(root);
    let min;
    
    for (let i = 1; i < sortedNode.length; i++) {
        if (!min) {
            min = Math.abs(sortedNode[0] - sortedNode[i]);
            continue;
        }
        
        const diff = Math.abs(sortedNode[i-1] - sortedNode[i]);
        
        if (min > diff) {
            min = diff;
        }
    }
    
    function getSortedNode(root, acc = []) { 
        const left = [];
        const right = [];
        
        if (root.left) {
            left.push(...getSortedNode(root.left));
        }

        if (root.right) {
            right.push(...getSortedNode(root.right));
        }

        const result = [...left, root.val, ...right];

        return result;        
    }
    
    return min;
};

내 코드의 경우 left, right배열을 두개 만들어주었는데 인터넷 참고 코드처럼 배열 하나로도 해결 할 수 있었다.

다들 아시겠지만 인터넷 참고 코드는 공간 복잡도가 내 코드랑 비교하여 더 낮다.

트리 순회에 대해 배운 알고리즘이다.

 

끝!