[Binary Search Tree (BST)] Minimum Absolute Difference in BST

530. Minimum Absolute Difference in BST

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

본 문제는 해결하지 못했습니다.

/**
 * 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}
 */
var getMinimumDifference = function(root) {
  const arr = dfsRecursivePostOrder(root);
  let min = Number.MAX_SAFE_INTEGER;  

  while(arr.length) {
    const root = arr.pop();
    const right = arr.pop();
    const left = arr.pop();

    min = Math.min((right - root), (root - left));    

    if(arr.length > 1) {
      arr.push(left);  
    }
  }

  return min;
};


var dfsRecursivePostOrder = function (node, arr = []) {
  if(node) {
    if(node.left) 
      dfsRecursivePostOrder(node.left, arr);

    if(node.right) 
      dfsRecursivePostOrder(node.right, arr);
      
    arr.push(node.val);
  }
  return arr;
}

본 로직은 완전 이진 트리에서는 테스트 케이스를 통과하나, 그렇지 않은 트리는 통과할 수 없습니다.

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

2-1. Using inorder

해답의 전문은 링크를 확인해주세요.

 /**
  * Runtime	: 69 ms
  * Memory	: 48.58 MB
  */
var getMinimumDifference = function(root) {
  let arr = [];
  function inOrder(node){
    if(node){
      inOrder(node.left);
      arr.push(node.val);
      inOrder(node.right);
    }
  }
  // inOrder will increasing order in BST
  inOrder(root);

  // because of increasing order we find minimum difference by travelling linearly once
  let minDiff = arr[1]-arr[0];
  for(let i=2; i<arr.length; i++){
    minDiff = Math.min(minDiff, arr[i]-arr[i-1]);
  }
  return minDiff;
};

필자는 같은 level에서 부모와 자식간의 최솟값을 구해야 한다고 잘못 이해했습니다. 지문에 적힌 the minimum absolute difference between the values of any two different nodes in the tree.에서 any two different nodes에 초점을 두지 못했습니다.