informasi kontak saya
Surat[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Pertanyaan ini masih tentang traversal sekuensial lapisan, namun prosesnya sedikit berbeda.
Pemikiran awal saya tentang pertanyaan ini salah karena awalnya saya memikirkannya berdasarkan gambar ini. Saya pikir saya hanya perlu memperluas node terakhir dari setiap lapisan dan hanya itu. Namun hal tersebut sebenarnya salah. Jika Anda mengikuti ide ini, jika tidak ada node 4 pada gambar di atas, maka node 5 tidak dapat ditambahkan ke kumpulan hasil sama sekali. Jadi ide ini tidak disarankan.
Ide yang benar:
Untuk mencegah keadaan di atas, sisi kiri juga bisa diperluas. Jadi penanganan yang benar adalah. Setiap lapisan dan setiap node perlu diperluas, tetapi hanya elemen terakhir dari setiap lapisan yang perlu ditambahkan ke kumpulan hasil.
Bagaimana cara menulis elemen terakhir yang akan ditambahkan ke kumpulan hasil?
Setiap lapisan menggunakan ukuran, jadi perhatikan penghitungan selama perulangan for, dan kumpulkan hasilnya pada lapisan terakhir.
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;
}
}
Temukan saja nilai rata-rata untuk setiap lapisan.Ini masih pertanyaan dewan
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;
}
}
Ini juga merupakan pertanyaan templat, pertahankan nilai maksimum saat memproses setiap baris.
Satu-satunya hal yang perlu diingat adalah nilai minimum int adalah 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;
}
}
Saya baru saja mengubah metode perluasan. Daripada memperluas subpohon kiri dan kanan, saya langsung menambahkan daftar anak ke tumpukan.
Ada metode yang digunakan di dalamnya yang perlu dipelajari.
ArrayDeque mengimplementasikan Deque, dan Deque mewarisi antarmuka Queue, dan Queue mewarisi antarmuka Collection, sehingga memiliki metode addAll. Mengenai parameter addAll, tipe parameternya adalah tipe Collection, yang berarti dapat menerima objek apa pun yang mengimplementasikan antarmuka Collection. Ini mencakup setiap struktur kolom yang dapat Anda pikirkan.
/*
// 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;
}
}
Ide: Perbedaan dari traversal sekuensial lapisan adalah adanya perubahan saat memproses setiap lapisan. Saat mencapai setiap lapisan, simpul pertama perlu dikeluarkan secara terpisah, tentunya harus diperluas terlebih dahulu setelah dikeluarkan, karena masih ada lapisan berikutnya. Kemudian mulailah melintasi node yang tersisa pada lapisan tersebut. Traversal ini terutama diimplementasikan berdasarkan ukuran antrian saat ini. Karena node pertama dari lapisan ini telah dikeluarkan, saya memulai dari =1 selama traversal. Apa yang perlu dilakukan selama pemrosesan setiap node adalah memodifikasi penunjukannya. Artinya, node berikutnya dari node pertama menunjuk ke node kedua yang muncul dari tumpukan kemudian, dan kemudian skr berpindah ke node berikutnya. Dan ingatlah untuk memperluas node anak kiri dan kanan selama proses ini.
/*
// 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;
}
}
Ia telah mengabdikan dirinya untuk meneliti teknologi selama lebih dari 30 tahun, dan mahir dalam berbagai bahasa seperti java, linux, javascript, php, css, dll. "Saya telah memberikan banyak kontribusi di bidang dokumentasi pengembang stasiun sumber terbuka untuk berbagi beberapa masalah dalam pengembangan teknologi untuk referensi di masa mendatang. Semua orang memeriksanya
Surat[email protected]