τα στοιχεία επικοινωνίας μου
Ταχυδρομείο[email protected]
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 κληρονομεί τη διεπαφή συλλογής, επομένως έχει τη μέθοδο addAll. Όσον αφορά τις παραμέτρους του addAll, ο τύπος παραμέτρου του είναι Collection type, που σημαίνει ότι μπορεί να λάβει οποιοδήποτε αντικείμενο που υλοποιεί τη διεπαφή 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;
}
}
Ιδέα: Η διαφορά από τη διαδοχική διέλευση επιπέδου είναι ότι υπάρχουν αλλαγές κατά την επεξεργασία κάθε επιπέδου. Όταν φτάσετε σε κάθε επίπεδο, ο πρώτος κόμβος πρέπει να αφαιρεθεί ξεχωριστά, φυσικά, πρέπει να επεκταθεί πρώτα μετά την απομάκρυνσή του, γιατί υπάρχει ακόμα το επόμενο στρώμα. Στη συνέχεια, αρχίστε να διασχίζετε τους υπόλοιπους κόμβους του επιπέδου. Η διέλευση υλοποιείται κυρίως από το μέγεθος του τρέχοντος que, δεδομένου ότι ο πρώτος κόμβος αυτού του επιπέδου έχει αφαιρεθεί, το i ξεκινά από το =1 κατά τη διάρκεια της διέλευσης. Αυτό που πρέπει να γίνει κατά την επεξεργασία κάθε κόμβου είναι να τροποποιηθεί η κατάδειξη. Δηλαδή, ο επόμενος κόμβος του πρώτου κόμβου δείχνει στον δεύτερο κόμβο που βγήκε από τη στοίβα αργότερα και, στη συνέχεια, το 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 κ.λπ. Έχει κάνει πολλές συνεισφορές στον τομέα του ανοιχτού κώδικα σταθμός τεκμηρίωσης προγραμματιστή για να μοιραστείτε ορισμένα ζητήματα στην ανάπτυξη τεχνολογίας για μελλοντική αναφορά
Ταχυδρομείο[email protected]