質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.46%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

Q&A

解決済

1回答

898閲覧

Java二分探索でダミーノードを利用する理由

macaroni323

総合スコア31

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

0グッド

0クリップ

投稿2021/06/09 21:48

Leetcodeで以下の問題を解いています。
117. Populating Next Right Pointers in Each Node II
イメージ説明

次の右ノードを指すように,各 next ポインタを生成します
次の右ノードが存在しない場合,次のポインタはNULLに設定されるべきでです
初期状態では,すべての次のポインタはNULLに設定されています.

この問題がわからず、解説動画を見ています。
解説動画
この解説動画でのコードは次の通りになります。これでコードはAcceptされるのですが、、
何点か理解できない箇所があります。
1:なぜ
Node head = root;
を設定するのでしょうか。rootをそのまま使うのはだめなのでしょうか。

2:なぜdummyをtempに入れるのでしょうか。
Node dummy = new Node(0);
Node temp = dummy;

3:なぜhead = dummy.next;で値が取れるのでしょうか。
ループ内ではtempにしか値を入れていないのに、なぜdummy.nextに値があるのでしょうか
Node temp = dummy;することにより、dummyでもtempの値が参照できているということなのでしょうか。

java

1/* 2// Definition for a Node. 3class Node { 4 public int val; 5 public Node left; 6 public Node right; 7 public Node next; 8 9 public Node() {} 10 11 public Node(int _val) { 12 val = _val; 13 } 14 15 public Node(int _val, Node _left, Node _right, Node _next) { 16 val = _val; 17 left = _left; 18 right = _right; 19 next = _next; 20 } 21}; 22*/ 23 24class Solution { 25 public Node connect(Node root) { 26 if(root == null) return null; 27 Node head = root; 28 while(head != null){ 29 Node dummy = new Node(0); 30 Node temp = dummy; 31 while(head !=null ){ 32 if(head.left != null){ 33 temp.next = head.left; 34 temp = temp.next; 35 } 36 if(head.right != null){ 37 temp.next = head.right; 38 temp = temp.next; 39 } 40 head = head.next; 41 } 42 head = dummy.next; 43 } 44 return root; 45 46 } 47}

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

1:なぜ

Node head = root;
を設定するのでしょうか。rootをそのまま使うのはだめなのでしょうか。

2:なぜdummyをtempに入れるのでしょうか。

Node dummy = new Node(0);
Node temp = dummy;

実際にためしてうまく動かないのを確認すればよいと思いますが・・・

ループの中で、headおよびtempは再代入が行われているため
ループの外側で変数を退避させています。

ノードを再帰的に処理しているので、ノードの先頭を保持している。

1だったら、
head = dummy.next;
return root;

の2行を見れば、rootに対して、直接

root = dummy.next;

と、やってはいけないことが想像できると思います。
本例、returnするはずのrootが変わっている。

2も同様に、

head = dummy.next
を取得したいが、temp自体は、
temp = temp.next;
で、上書きされる。

なので、上書き前のノードを保存している
ちなみに

Node temp = new Node(0);
Node dummy = temp;

の方が、わかりやすい気がする。

3:なぜhead = dummy.next;で値が取れるのでしょうか。

ループ内ではtempにしか値を入れていないのに、なぜdummy.nextに値があるのでしょうか
Node temp = dummy;することにより、dummyでもtempの値が参照できているということなのでしょうか。

その認識でOK

temp.next = head.left;//head.right;

の部分で設定される。

投稿2021/06/09 23:17

momon-ga

総合スコア4820

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

macaroni323

2021/06/10 08:43

ありがとうございました!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.46%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問