drop-of-water

문제 링크

조건

  • 노드의 갯수 [2, 1000].
  • -2^31 <= Node.val <= 2^31 - 1
  • 정확히 두 개의 노드의 값이 바뀌어진 상태

입력값

  • root = 바이너리 서치 트리 root

출력값

  • 없음 (in place로 바이너리 서치 트리 값만 수정)

풀이과정

  • inorder traverse를 진행하면서 잘못된 위치의 노드를 first, second에 저장
  • traverse를 완료 후 first, second의 값을 swap

코드

var recoverTree = function (root) {
  let first, second, prev;
  function traverse(root) {
    if (!root) return;
    traverse(root.left);
    if (prev && prev.val > root.val) {
      if (!first) first = prev;
      second = root;
    }

    prev = root;
    traverse(root.right);
  }

  traverse(root);

  let tmp = first.val;
  first.val = second.val;
  second.val = tmp;
};

😊