実際にバイナリツリーを反転する方法については

あなたは、その垂直軸の上に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番目に移動すると2と3に遭遇しますので、スワップして取得します.

  1
 / \
3   2

おもしろい、これはそれを逆にしたようです!つ以上のノードがあるときにスワッピングと同じくらい簡単ですか?
どのような2つ以上のノードを1つのレベルごとにスワップする必要がありますか?追加のレベルがあれば、次のようになります.

      1
     / \
    3   2
   / \   \
  4   5   3

最終的な行は、現在242479142に指示されます、しかし、我々は結果が適切に逆にされる4 -> 5 -> 3であることを望みます.
しかし、我々は2つの別々のスワップをすることによってこれを達成することができます.3 -> 5 -> 4および4をスワップして5を取得し、5 -> 4で5 -> 4をスワップした場合には、以下のようになります.

      1
     / \
    2   3
   /   / \
  3   5   4

それで、一緒にすべてを置くために:私たちは、順序をたどることができて、各々の反復でスワップをすることができます.

読者によって指摘された警告-私たちが実質的に大きな二分木に対処しているなら、再帰的な解決は呼び出しスタックサイズのために問題を引き起こすかもしれません.これを回避するには2つの方法があります.
は、再帰を模倣するために、スタックを使用します
待ち行列を使用して、BFSファッションで1つずつレベルを訪問して、木を倒すために左右のノードを交換して、

.

最終的なコードは次のようになります.

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を試してみてください!