Java でのバイナリ ツリーの反転

最近、アルゴリズム/データ構造のスキルを向上させるために、LeetCode の演習をいくつか練習し始めました。このプラットフォームは、他の開発者と複数のプログラミング言語でソリューションを練習して学習したり、他の開発者とソリューションを議論したり共有したり、大企業から要求されたコードの課題を練習したりするのに適した環境を提供していると言えます。

LeetCodeとは何ですか?

LeetCode は、候補者がコーディング面接の準備をするのに役立つ Web サイトです。ユーザーは、候補者の解決策に対する事前定義されたテストとともに、プラットフォームのコーディングおよびアルゴリズムの問​​題を使用して課題を練習できます。 LeetCode は、HackerRank と並んで、技術面接やコーディング コンテストの人気リソースとなっています。

私のルーチンの問題解決

私は 1 日に少なくとも 3 つの課題を解決するという目標を掲げており、解決策の考え方には iPad、画面用のペン、Freeform アプリを使用しています。私は解決策を描いて考えるようにしていますが、これはコードの提出に大いに役立っています。多くの課題は一見すると難しそうに見えますが、数分で解決策を考え、設計することができます (思考プロセスを書き留めることをお勧めします)。 30 分以内に適切な解決策が見つからない場合は、他の開発者からの提出物を見て、自分の間違い (コード内で忘れていた小さなステップ) がどこにあるのかを見つけます。あなたのソリューションが十分に優れている場合でも、他の人が提出したものを見て、その問題を解決する別の方法 (多かれ少なかれ効率的) を考えることを強くお勧めします。

逆二分木問題

数日前、私は LeetCode で Invert Binary Tree 問題に直面しました。これはいくつかのインタビューで要求されたよく知られた課題であり、大学でデータ構造/アルゴリズムのクラスを受講したときに見た問題でもありました。私は面接でこのような課題に直面したことはなく、仕事で二分木を明示的に反転したこともありませんでしたが、二分木を反転する方法を知ることで、DS、ツリー、アルゴリズムの考え方についてより多くの経験を積むことができ、再帰などのいくつかのテクニックを練習することができました。
この記事の残りを読む前に、この問題を解決してみることをお勧めします

解決策

二分木の反転問題では、「二分木のルートが与えられた場合、その木を反転し、そのルートを返す」ように求められました。 (言い換えれば、ツリーを「ミラーリング」する必要があります)。 Java プログラミング言語を使用してソリューションを送信しましたが、手順は他の言語でも同じです (構文が少し変更されています)。入力例と予想される出力を以下に示します。

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

再帰手法を使用して invertTree() メソッドを再帰的に呼び出し、ツリーのある側面をルートとして渡します。したがって、すべての再帰で要求されるように、再帰スタックが終了して再帰呼び出しのそれぞれの結果を返す停止条件を定義する必要があります。その後、ツリーの側面を反転して、root.right をパラメータとして渡す再帰によって返された値を root.left に割り当て、同じことを root.right に行い、root.left 再帰結果の値を割り当てます。 元の値を変更しているため、root.left の元の結果を保存するための補助変数が必要です (おそらく大学でこのようなコードを実装し、swap() メソッドと呼んでいたでしょう。

最後に、ノードを反転したルートを返します。以下のコードを確認できます:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }

        TreeNode aux = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(aux);

        return root;
    }
}

さまざまな問題に対してさまざまな解決策が存在する可能性があることを覚えておいてください。それは素晴らしいことです。誰もが考え方やプログラム、データ構造ドメインなどを持っています。この問題を解決するためにまったく同じコードに従う必要はありませんが、アルゴリズムの複雑さに注意を払う必要があります (問題を解決するには 3 つのネストを使用できます)ただし、これは 1 を使用するよりもパフォーマンスが低くなります。

以上がJava でのバイナリ ツリーの反転の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。