Rust Algorithm Bites – Binärbaum Level-Order-Traversierung
LeetCode 102 meistern: Binärbaum Level-Order-Traversierung mit einem BFS-Ansatz in Rust, unter Verwendung von Rc, RefCell und VecDeque für effiziente Baum-Traversierung.
Problemstellung
LeetCode 102: Binary Tree Level Order Traversal (Link)
Gegeben sei ein Binärbaum. Gib seine Level-Order-Traversierung als Vektor von Vektoren zurück (d.h. Knoten gruppiert nach Tiefenebene).
Beispiel:
3
/ \
9 20
/ \
15 7
Ausgabe:
[
[3],
[9,20],
[15,7]
]
Algorithmus-Idee
Das Problem dreht sich darum, Knoten Ebene für Ebene zu besuchen. Es gibt zwei Standardansätze:
- Iteratives BFS mit einer Queue – verwende eine VecDeque, um jeweils eine Ebene zu verarbeiten.
- Rekursives DFS mit Level-Tracking – führe die aktuelle Tiefe mit und füge Werte in den richtigen Bucket ein.
Beide erreichen dasselbe Ergebnis, aber BFS ist normalerweise klarer für "Level Order".
Der Rust-Aspekt
Hier wird das Problem in Rust zu mehr als nur "benutze eine Queue":
- Binärbäume in Rust sind nicht trivial. Wegen der Ownership-Regeln wrappen wir Kind-Zeiger in
Rc<RefCell<TreeNode>>.Rc→ Reference Counting für geteilte Ownership.RefCell→ Interior Mutability, sodass wir Knoten zur Laufzeit mutable ausleihen können.
- Bei BFS ist die Hauptdesign-Entscheidung, ob wir die Ownership der Kinder übernehmen oder nur Referenzen klonen:
take()der Kinder → reduziert Speicherverbrauch, aber mutiert den Baum.- Clone
Rc→ bewahrt den ursprünglichen Baum, verwendet aber etwas mehr Speicher. - Pattern Matching mit
Optionist hier ein zentrales Rust-Idiom.
Erste Iterationslösung (Idiomatisches BFS)
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
pub val: i32,
pub left: Option<Rc<RefCell<TreeNode>>>,
pub right: Option<Rc<RefCell<TreeNode>>>,
}
impl TreeNode {
#[inline]
pub fn new(val: i32) -> Self {
TreeNode { val, left: None, right: None }
}
}
struct Solution;
impl Solution {
pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
let mut result = vec![];
let mut queue = VecDeque::new(); // Hinweis: wie vec, aber mit Queue-Accessoren
if let Some(node) = root {
queue.push_back(node); // 1. hier fügen wir den Root-Knoten zur Queue hinzu
}
// Hinweis: hier verarbeiten wir die verfügbaren Queue-Elemente, erst 1, dann 2, dann 4 usw.
while !queue.is_empty() {
let n = queue.len();
let mut level = Vec::with_capacity(n);
for _ in 0..n {
if let Some(node) = queue.pop_front() {
let node_ref = node.borrow();
level.push(node_ref.val); // 2. Knotenwert zur aktuellen Ebene hinzufügen
// todo: linken und rechten Knoten ebenfalls verarbeiten
}
}
result.push(level); // 3. aktuelle Ebene zum Ergebnis hinzufügen
}
result
}
}
Was passiert hier?
- Nimmt den ersten Root-Knoten und fügt ihn zur Queue hinzu
- Fügt den Wert des Knotens aus der Queue zur Level-Ergebnisliste hinzu
- Fügt die Level-Ergebnisliste zur Gesamtergebnisliste hinzu
Testen wir diesen Code bisher:
#[test]
fn test() {
// [3,9,20,null,null,15,7]
let mut root = TreeNode {
val: 3,
left: Some(Rc::new(RefCell::new(TreeNode {
val: 9,
left: None,
right: None,
}))),
right: Some(Rc::new(RefCell::new(TreeNode {
val: 20,
left: Some(Rc::new(RefCell::new(TreeNode {
val: 15,
left: None,
right: None,
}))),
right: Some(Rc::new(RefCell::new(TreeNode {
val: 7,
left: None,
right: None,
}))),
}))),
};
assert_eq!(
Solution::level_order(Some(Rc::new(RefCell::new(root)))),
vec![vec![3]]
);
}
Ok, das läuft grün, super.
Jetzt machen wir den vollständigen Test grün:
#[test]
fn test() {
// .. genau wie oben
assert_eq!(
Solution::level_order(Some(Rc::new(RefCell::new(root)))),
vec![vec![3], vec![9, 20], vec![15, 7]]
);
}
Wir müssen die linken und rechten Kindknoten zur Queue hinzufügen. Die Schleife wird dann die nächste Ebene weiter verarbeiten. Mit anderen Worten: Batches, die zur Queue hinzugefügt werden, werden als dieselbe Ebene verarbeitet. Das sieht dann so aus:
// .. alles wie vorher
for _ in 0..n {
if let Some(node) = queue.pop_front() {
let node = node.borrow();
level.push(node.val);
// 1. wenn wir einen linken Knoten haben, zur Queue hinzufügen
if let Some(left) = node.left.as_ref() {
queue.push_back(left.clone());
}
// 2. dasselbe für den rechten Knoten
if let Some(right) = node.right.as_ref() {
queue.push_back(right.clone());
}
}
}
// .. alles wie vorher
Vollständige Lösung (Idiomatisches BFS)
use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
pub val: i32,
pub left: Option<Rc<RefCell<TreeNode>>>,
pub right: Option<Rc<RefCell<TreeNode>>>,
}
impl TreeNode {
#[inline]
pub fn new(val: i32) -> Self {
TreeNode { val, left: None, right: None }
}
}
struct Solution;
impl Solution {
pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
let mut result = vec![];
let mut queue = VecDeque::new();
if let Some(root) = root {
queue.push_back(root);
}
while !queue.is_empty() {
let n = queue.len();
let mut level = Vec::with_capacity(n);
for _ in 0..n {
if let Some(node) = queue.pop_front() {
let node = node.borrow();
level.push(node.val);
if let Some(left) = node.left.as_ref() {
queue.push_back(left.clone());
}
if let Some(right) = node.right.as_ref() {
queue.push_back(right.clone());
}
}
}
result.push(level);
}
result
}
}
Rekursives DFS mit Level-Tracking (Bonustrack)
Statt Breitensuche können wir auch Tiefensuche machen und die aktuelle Ebene tracken. Das ist etwas aufwendiger, aber eine gute Übung in Rekursion und Zustandsverwaltung.
// .. Imports und Baumstruktur wie vorher
impl Solution {
// mit Rekursion
pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
let level = 0;
let mut result = vec![];
Self::add_to_level(root, &mut result, level);
result
}
fn add_to_level(root: Option<Rc<RefCell<TreeNode>>>, result: &mut Vec<Vec<i32>>, level: usize) {
if let Some(root) = root.as_ref() {
while result.len() <= level {
result.push(vec![]);
}
// 1. füge den aktuellen Knotenwert zur richtigen Ebene hinzu
// oben stellen wir sicher, dass die Ebene existiert
result[level].push(root.borrow().val);
let next_level = level + 1;
// 3. rekursiere links mit erhöhter Ebene
let left = root.borrow().left.clone();
Self::add_to_level(left, result, next_level);
// 4. rekursiere rechts mit erhöhter Ebene
let right = root.borrow().right.clone();
Self::add_to_level(right, result, next_level);
}
}
}
Dieser Ansatz verwendet Rekursion, um den Baum zu traversieren. Die add_to_level-Funktion prüft, ob ein Vektor für die aktuelle Ebene existiert; falls nicht, erstellt sie einen. Dann verarbeitet sie rekursiv die linken und rechten Kinder und erhöht dabei die Ebene für jeden Abstieg.
Fazit
Sowohl BFS- als auch DFS-Ansätze sind gültig für Level-Order-Traversierung. Der BFS-Ansatz ist oft intuitiver für dieses spezifische Problem, während der DFS-Ansatz Rekursion und Zustandsverwaltung in Rust demonstriert. Das Verständnis der Arbeit mit Rc und RefCell ist entscheidend beim Umgang mit Baumstrukturen in Rust, was diese Übung zu einer großartigen Möglichkeit macht, deine Rust-Fähigkeiten zu vertiefen.
Außerdem ist VecDeque eine praktische Datenstruktur in Rust für Queue-Operationen und bietet effiziente Push- und Pop-Operationen von beiden Enden.
Herausforderung
Erweitere die Lösung für folgende Varianten:
- Rechts-nach-Links Level Order: Gib stattdessen
[[3],[20,9],[7,15]]zurück - Zickzack Level Order: Wechsle zwischen links-nach-rechts und rechts-nach-links:
[[3],[20,9],[15,7]] - Generischer Baum: Lass es mit
TreeNode<T>funktionieren, wobeiT: Clone + Debug
Bonus: Implementiere eine Version, die mit Box<TreeNode> statt Rc<RefCell<TreeNode>> arbeitet und vergleiche die Ergonomie.