我們直接用範例來看函式呼叫和遞迴的關係。
題目：給一棵二元樹，計算這顆樹有幾層
輸入：root = [3,9,20,null,null,15,7]
輸出：3
解法1：使用遞迴，先往下走到葉節點時深度為0，再往上走並回傳左右子樹較深的值，直到根節點就能知道最深是多少。
// Definition for a binary tree node.
// #[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
// }
// }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
match root {
None => 0,
Some(node) => {
let l_depth = Self::max_depth(node.borrow().left.clone());
let r_depth = Self::max_depth(node.borrow().right.clone());
return l_depth.max(r_depth)+1;
}
}
}
}
每一次函式呼叫Self::max_depth()，rust都會建立一個「stack frame」
程式執行時會使用一塊記憶體叫「呼叫堆疊（call stack）」。
每當你呼叫一次，系統會把這個函式的「參數、區域變數、返回位址」放進一個stack frame。
這個 frame 會放到 call stack 上（像資料結構的 stack.push）。
2. 當函式執行結束，stack frame 被彈出（pop）
leetcode 104例子 樹大概如下
3
/ \
9 20
/ \
15 7
1. max_depth(3)
2. ├── max_depth(9)
3. │ ├── max_depth(None)
4. │ └── max_depth(None)
5. └── max_depth(20)
6. ├── max_depth(15)
7. │ ├── max_depth(None)
8. │ └── max_depth(None)
9. └── max_depth(7)
10. ├── max_depth(None)
11. └── max_depth(None)
上圖為stack呼叫順序，呼叫後就要往下一層走，直到有回傳值
呼叫root max_depth(node3)
呼叫node3左子樹max_depth(node9)找最深深度
呼叫node9左子樹，因為左子樹的是None回傳0
呼叫node9右子樹，因為右子樹的是None回傳0
回傳max_depth(node9)=1
呼叫node3右子樹max_depth(node20)找最深深度
呼叫node20左子樹Self::max_depth(node15);
呼叫node15左子樹，因為左子樹的是None回傳0
呼叫node15右子樹，因為右子樹的是None回傳0
回傳max_depth(node15)=1
呼叫node20右子樹Self::max_depth(node7);
呼叫node7左子樹，因為左子樹的是None回傳0
呼叫node7右子樹，因為右子樹的是None回傳0
回傳max_depth(node7)=1
回傳max_depth(node20)=2
回傳max_depth(node3)=3
如果你的遞迴很深（像是深度上萬層的二元樹），你就會遇到
thread 'main' has overflowed its stack
可以看到系統分配的stack爆了，這時可以自己用Vec寫stack來模擬Last In First Out，因為Vec，存放在 heap 上，空間比較大
解法2：使用stack來存節點和深度
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
if let None = root {
return 0
}
let mut stack:Vec<(Rc<RefCell<TreeNode>>,i32)> = Vec::new();
let mut depth = 0;
stack.push((root.unwrap(),1));
while let Some((node,current_depth)) = stack.pop() {
if let Some(left) = node.borrow().left.clone() {
stack.push((left,current_depth+1));
}
if let Some(right) = node.borrow().right.clone() {
stack.push((right,current_depth+1));
}
depth = depth.max(current_depth);
}
depth
}
}
fn generate_deep_tree(depth: i32) -> Option<Rc<RefCell<TreeNode>>> {
let mut root = Rc::new(RefCell::new(TreeNode::new(0)));
let mut current = root.clone();
for i in 1..depth {
let new_node = Rc::new(RefCell::new(TreeNode::new(i)));
current.borrow_mut().right = Some(new_node.clone());
current = new_node;
}
Some(root)
}
結果：stack overflow
use std::rc::Rc;
use std::cell::RefCell;
// 定義二元樹節點
#[derive(Debug)]
pub struct TreeNode {
pub val: i32,
pub left: Option<Rc<RefCell<TreeNode>>>,
pub right: Option<Rc<RefCell<TreeNode>>>,
}
impl TreeNode {
pub fn new(val: i32) -> Self {
TreeNode {
val,
left: None,
right: None,
}
}
}
pub struct Solution;
impl Solution {
pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
match root {
None => 0,
Some(node) => {
let l_depth = Self::max_depth(node.borrow().left.clone());
let r_depth = Self::max_depth(node.borrow().right.clone());
return l_depth.max(r_depth)+1;
}
}
}
}
fn main() {
let depth = 1_000_000;
let root = generate_deep_tree(depth);
let result = Solution::max_depth(root);
println!("Max depth = {}", result);
}
fn generate_deep_tree(depth: i32) -> Option<Rc<RefCell<TreeNode>>> {
let mut root = Rc::new(RefCell::new(TreeNode::new(0)));
let mut current = root.clone();
for i in 1..depth {
let new_node = Rc::new(RefCell::new(TreeNode::new(i)));
current.borrow_mut().right = Some(new_node.clone());
current = new_node;
}
Some(root)
}
//thread 'main' has overflowed its stack
//fatal runtime error: stack overflow, aborting
結果：印出Max depth = 1000000
use std::rc::Rc;
use std::cell::RefCell;
// 定義二元樹節點
#[derive(Debug)]
pub struct TreeNode {
pub val: i32,
pub left: Option<Rc<RefCell<TreeNode>>>,
pub right: Option<Rc<RefCell<TreeNode>>>,
}
impl TreeNode {
pub fn new(val: i32) -> Self {
TreeNode {
val,
left: None,
right: None,
}
}
}
pub struct Solution;
impl Solution {
pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
if let None = root {
return 0
}
let mut stack:Vec<(Rc<RefCell<TreeNode>>,i32)> = Vec::new();
let mut depth = 0;
stack.push((root.unwrap(),1));
while let Some((node,current_depth)) = stack.pop() {
if let Some(left) = node.borrow().left.clone() {
stack.push((left,current_depth+1));
}
if let Some(right) = node.borrow().right.clone() {
stack.push((right,current_depth+1));
}
depth = depth.max(current_depth);
}
depth
}
}
fn main() {
let depth = 1_000_000;
let root = generate_deep_tree(depth);
let result = Solution::max_depth(root);
println!("Max depth = {}", result);
}
fn generate_deep_tree(depth: i32) -> Option<Rc<RefCell<TreeNode>>> {
let mut root = Rc::new(RefCell::new(TreeNode::new(0)));
let mut current = root.clone();
for i in 1..depth {
let new_node = Rc::new(RefCell::new(TreeNode::new(i)));
current.borrow_mut().right = Some(new_node.clone());
current = new_node;
}
Some(root)
}
//Max depth = 1000000
iThome鐵人賽
看影片追技術
看更多