ホームページ Java &#&チュートリアル Java でのバイナリ ツリーの反転

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

Oct 02, 2024 am 08:07 AM

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

LeetCodeとは何ですか?

Inverting a binary tree in Java

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

私のルーチンの問題解決

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

逆二分木問題

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

解決策

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

Inverting a binary tree in Java

1

2

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() メソッドと呼んでいたでしょう。

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

/**

 * 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 サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

Video Face Swap

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

会社のセキュリティソフトウェアはアプリケーションの実行に失敗していますか?それをトラブルシューティングと解決する方法は? 会社のセキュリティソフトウェアはアプリケーションの実行に失敗していますか?それをトラブルシューティングと解決する方法は? Apr 19, 2025 pm 04:51 PM

一部のアプリケーションが適切に機能しないようにする会社のセキュリティソフトウェアのトラブルシューティングとソリューション。多くの企業は、内部ネットワークセキュリティを確保するためにセキュリティソフトウェアを展開します。 ...

名前を数値に変換してソートを実装し、グループの一貫性を維持するにはどうすればよいですか? 名前を数値に変換してソートを実装し、グループの一貫性を維持するにはどうすればよいですか? Apr 19, 2025 pm 11:30 PM

多くのアプリケーションシナリオでソートを実装するために名前を数値に変換するソリューションでは、ユーザーはグループ、特に1つでソートする必要がある場合があります...

MapsTructを使用したシステムドッキングのフィールドマッピングの問題を簡素化する方法は? MapsTructを使用したシステムドッキングのフィールドマッピングの問題を簡素化する方法は? Apr 19, 2025 pm 06:21 PM

システムドッキングでのフィールドマッピング処理は、システムドッキングを実行する際に難しい問題に遭遇することがよくあります。システムのインターフェイスフィールドを効果的にマッピングする方法A ...

Intellijのアイデアは、ログを出力せずにSpring Bootプロジェクトのポート番号をどのように識別しますか? Intellijのアイデアは、ログを出力せずにSpring Bootプロジェクトのポート番号をどのように識別しますか? Apr 19, 2025 pm 11:45 PM

intellijideaultimatiateバージョンを使用してスプリングを開始します...

エンティティクラス変数名をエレガントに取得して、データベースクエリ条件を構築する方法は? エンティティクラス変数名をエレガントに取得して、データベースクエリ条件を構築する方法は? Apr 19, 2025 pm 11:42 PM

データベース操作にMyBatis-Plusまたはその他のORMフレームワークを使用する場合、エンティティクラスの属性名に基づいてクエリ条件を構築する必要があることがよくあります。あなたが毎回手動で...

Javaオブジェクトを配列に安全に変換する方法は? Javaオブジェクトを配列に安全に変換する方法は? Apr 19, 2025 pm 11:33 PM

Javaオブジェクトと配列の変換:リスクの詳細な議論と鋳造タイプ変換の正しい方法多くのJava初心者は、オブジェクトのアレイへの変換に遭遇します...

Redisキャッシュソリューションを使用して、製品ランキングリストの要件を効率的に実現する方法は? Redisキャッシュソリューションを使用して、製品ランキングリストの要件を効率的に実現する方法は? Apr 19, 2025 pm 11:36 PM

Redisキャッシュソリューションは、製品ランキングリストの要件をどのように実現しますか?開発プロセス中に、多くの場合、ランキングの要件に対処する必要があります。

eコマースプラットフォームSKUおよびSPUデータベースデザイン:ユーザー定義の属性と原因のない製品の両方を考慮する方法は? eコマースプラットフォームSKUおよびSPUデータベースデザイン:ユーザー定義の属性と原因のない製品の両方を考慮する方法は? Apr 19, 2025 pm 11:27 PM

eコマースプラットフォーム上のSKUおよびSPUテーブルの設計の詳細な説明この記事では、eコマースプラットフォームでのSKUとSPUのデータベース設計の問題、特にユーザー定義の販売を扱う方法について説明します。

See all articles