プライベートな連絡先の最初の情報
送料メール:
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
この質問は依然として層順次走査に関するものですが、処理は若干異なります。
この質問についての私の最初の考えは間違っていました。なぜなら、最初はこの絵に基づいて考えたからです。各レイヤーの最後のノードを展開するだけで十分だと思いました。しかし、それは実際には間違っています。この考え方に従う場合、上の図にノード 4 が存在しない場合、ノード 5 を結果セットにまったく追加できません。したがって、この考えはお勧めできません。
正しい考え:
上記の状況を防ぐために、左側を拡張することもできます。したがって、正しい取り扱いは次のとおりです。各レイヤーと各ノードを展開する必要がありますが、結果セットに追加する必要があるのは各レイヤーの最後の要素のみです。
結果セットに追加される最後の要素をどのように記述するか?
各レイヤーはサイズを使用するため、for ループ中のカウントに注意し、最後のレイヤーで結果を収集します。
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> que = new ArrayDeque<>();
if(root==null){
return result;
}
que.offerLast(root);
while(!que.isEmpty()){
int size = que.size();
for(int i = 0;i<size;i++){
TreeNode temp = que.pollFirst();
if(i==size-1){
result.add(temp.val);
}
if(temp.left!=null){
que.offerLast(temp.left);
}
if(temp.right!=null){
que.offerLast(temp.right);
}
}
}
return result;
}
}
各レイヤーの平均値を見つけるだけです。それはまだ理事会の質問です
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> result = new ArrayList<>();
Deque<TreeNode> que = new ArrayDeque<>();
if(root==null){
return result;
}
que.offerLast(root);
while(!que.isEmpty()){
int size = que.size();
double sum = 0;
double avg = 0;
for(int i = 0;i<size;i++){
TreeNode temp = que.pollFirst();
sum += temp.val;
if(temp.left!=null){
que.offerLast(temp.left);
}
if(temp.right!=null){
que.offerLast(temp.right);
}
}
avg = sum/size;
result.add(avg);
}
return result;
}
}
これはテンプレートの質問でもあり、各行を処理するときに最大値を維持するだけです。
覚えておくべき唯一のことは、int の最小値は Integer.MIN_VALUE であるということです。
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> que = new ArrayDeque<>();
if(root==null){
return result;
}
que.offerLast(root);
while(!que.isEmpty()){
int size = que.size();
int max = Integer.MIN_VALUE;
for(int i = 0;i<size;i++){
TreeNode temp = que.pollFirst();
if(temp.val > max){
max = temp.val;
}
if(temp.left!=null){
que.offerLast(temp.left);
}
if(temp.right!=null){
que.offerLast(temp.right);
}
}
result.add(max);
}
return result;
}
}
展開方法を変更して、左右のサブツリーを展開する代わりに、子リストをスタックに直接追加しました。
その中で使用されているメソッドがあり、それを学ぶ必要があります。
ArrayDeque は Deque を実装し、Deque は Queue インターフェイスを継承し、Queue は Collection インターフェイスを継承するため、addAll メソッドを持ちます。 addAll のパラメータに関しては、そのパラメータの型は Collection 型です。つまり、Collection インターフェイスを実装する任意のオブジェクトを受け取ることができます。これには、考えられるすべての列構造が含まれます。
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> result = new ArrayList<>();
Deque<Node> que = new ArrayDeque<>();
if(root == null){
return result;
}
que.offerLast(root);
while(!que.isEmpty()){
int size = que.size();
List<Integer> curList = new ArrayList<>();
while(size>0){
Node temp = que.pollFirst();
curList.add(temp.val);
//就是扩展方式变了，变为直接把子节点全部加入到队列中，这也等价于将里面的每个元素从尾部依次加入队列当中。
que.addAll(temp.children);
size--;
}
result.add(curList);
}
return result;
}
}
アイデア: レイヤー順次トラバーサルとの違いは、各レイヤーの処理時に変更があることです。各層に到達するときは、最初のノードを個別に取り出す必要があります。もちろん、取り出した後は次の層がまだあるため、最初にノードを展開する必要があります。次に、レイヤーの残りのノードの走査を開始します。走査は主に現在のキューのサイズによって実装されます。この層の最初のノードが取り出されているため、走査中は i は =1 から始まります。各ノードの処理中に行う必要があるのは、ポインティングを変更することです。つまり、最初のノードの次のノードは、後でスタックからポップされた 2 番目のノードを指し、その後 cur は次へ移動します。このプロセス中に、忘れずに左右の子ノードを展開してください。
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
Deque<Node> que = new ArrayDeque<>();
if(root==null){
return root;
}
que.offerLast(root);
while(!que.isEmpty()){
//每层先取出第一个节点
int size = que.size();
Node cur = que.pollFirst();
//扩展它
if(cur.left!=null){
que.offerLast(cur.left);
}
if(cur.right!=null){
que.offerLast(cur.right);
}
for(int i = 1;i<size;i++){
Node next = que.pollFirst();
if(next.left!=null){
que.offerLast(next.left);
}
if(next.right!=null){
que.offerLast(next.right);
}
cur.next = next;
cur = next;
}
}
return root;
}
}
彼は 30 年以上テクノロジーの研究に専念しており、Java、linux、javascript、php、css などのさまざまな言語に堪能であり、オープンソース分野で多くの貢献を行っています。将来の参考のために技術開発におけるいくつかの問題を共有する開発者ドキュメント ステーション。
送料メール: