Flatten Binary Tree to Linked List

문제 링크

• https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

조건

트리가 가지고 있는 노드의 갯수 [0, 2000]. -100 <= Node.val <= 100

입력값

• root = Binary Tree의 루트

출력값

• 없음 = 기존 트리 내용만 pre-order traversal 순서대로 + right child만 가지도록 (flatten) 변환

풀이과정

• leaf node 까지 traverse 한 후 left는 없애고
• right 에는 이전 node를 넣어주고
• prev에는 현재 node를 넣어주면서 밑에서부터 위로 traverse 진행

코드

var flatten = function (root) {
  let prev = null;

  traverse(root);
  function traverse(r) {
    if (!r) return;

    traverse(r.right);
    traverse(r.left);

    r.left = null;
    r.right = prev;
    prev = r;
  }
};

😊