이진 트리를 실제로 반전시키는 방법에 대한 시각적 가이드

binary tree를 수직축으로 뒤집을 수 있습니까? 이것은 이 트윗에 의해 유명해진 유명한 문제입니다.

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

— Max Howell (@mxcl)

다음과 같은 binary tree가 주어집니다.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

반전을 수행하면 다음과 같은 결과가 발생합니다.

Output:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

트리 노드의 정의는 다음과 같습니다.

function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

이 강의는 원래 https://algodaily.com에 게시되었으며, 여기서 저는 기술 인터뷰 과정을 유지하고 야심 찬 개발자를 위한 아이디어를 작성합니다.




이것은 Homebrew 저자Max Howell가 던진 유명한 질문입니다. 바라건대 이것은 당신이 같은 불행을 겪지 않도록 예방합니다!

무차별 대입에 대해 생각해 봅시다. 영리한 알고리즘 없이 어떻게 할 수 있을까요? 다음과 같이 매우 기본적인 입력으로 시작할 수 있습니다.

  1
 / \
2   3

따라서 세로로 반전하려면 뒤집거나 바꿀 것이 없는 1 에서 시작하고 그대로 둡니다. 이제 첫 번째 행을 처리했습니다.

두 번째로 이동하면 2 및 3 가 발생하므로 이를 교환하고 다음을 얻습니다.

  1
 / \
3   2

흥미롭게도 이것은 거꾸로 된 것 같습니다! 둘 이상의 노드가 있을 때 교환하는 것처럼 간단합니까?

그래도 레벨당 교체할 노드가 2개 이상인 경우에는 어떻게 됩니까? 추가 수준이 있는 경우 다음과 같이 표시될 수 있습니다.

      1
     / \
    3   2
   / \   \
  4   5   3

마지막 행은 현재 방향성이 있지만 4 -> 5 -> 3 결과가 적절하게 반전되길 원합니다.

그러나 두 개의 개별 스왑을 수행하여 이를 달성할 수 있습니다. 아래는 3 -> 5 -> 4 와 4 를 교환하여 5 를 얻은 다음 5 -> 4 를 5 -> 4 로 교환하면 얻을 수 있는 것입니다.

      1
     / \
    2   3
   /   / \
  3   5   4

따라서 모두 합치면 순서 순회를 수행하고 각 반복에서 스왑을 수행할 수 있습니다.



독자들이 지적한 주의 사항-- 상당히 큰 이진 트리를 다루는 경우 재귀 솔루션은 호출 스택 크기로 인해 문제를 일으킬 수 있습니다. 이 문제를 해결하는 방법에는 두 가지가 있습니다.

스택을 사용하여 재귀 모방

대기열을 사용하여 BFS 방식으로 레벨을 하나씩 방문하고 왼쪽 노드와 오른쪽 노드를 교환하여 트리를 반전시킵니다.

최종 코드는 다음과 같습니다.

function invertTree(head) {
  if (head) {
    var temp = head.left;
    head.left = head.right;
    head.right = temp;

    invertTree(head.left);
    invertTree(head.right);
  }

  return head;
}

technical challenges at AlgoDaily.com에 대한 더 많은 시각적 자습서를 확인하고 our daily coding problem newsletter을 사용해 보십시오!