用Rust🦀写算法-二叉树之遍历篇

144. 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]

输出：[1,2,3]

解释：

screenshot-2024-08-29-202743.png

示例 2：

输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出：[1,2,4,5,6,7,3,8,9]

解释：

tree_2.png

示例 3：

输入：root = []

输出：[]

示例 4：

输入：root = [1]

输出：[1]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

💡 思路：

  1. 递归法
  2. 迭代法

二叉树定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 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
    }
  }
}

代码（思路一）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn preorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut result = vec![];
        Self::traversal(&root, &mut result);
        result
    }

    fn traversal(root: &Option<Rc<RefCell<TreeNode>>>, result: &mut Vec<i32>) {
        if let Some(node) = root {
            let node = node.borrow(); // RefCell 获取不可变引用 TreeNode
            result.push(node.val);
            Self::traversal(&node.left, result);
            Self::traversal(&node.right, result);
        }
    }
}

代码（思路二）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn preorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut result = vec![];
        let mut stack = vec![];
        
        if let Some(node) = root {
            stack.push(node);
        }
        
        while let Some(node) = stack.pop() {
            // 1. 访问当前节点
            let node_ref = node.borrow();
            result.push(node_ref.val);
            
            // 2. 右子节点先入栈（后处理）
            if let Some(right) = &node_ref.right {
                stack.push(right.clone());
            }
            
            // 3. 左子节点后入栈（先处理）
            if let Some(left) = &node_ref.left {
                stack.push(left.clone());
            }
        }
        
        result
    }
}

145. 二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

输入：root = [1,null,2,3]

输出：[3,2,1]

解释：

screenshot-2024-08-29-202743.png

示例 2：

输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出：[4,6,7,5,2,9,8,3,1]

解释：

tree_2.png

示例 3：

输入：root = []

输出：[]

示例 4：

输入：root = [1]

输出：[1]

提示：

  • 树中节点的数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

💡 思路：

  1. 递归法
  2. 迭代法

代码（思路一）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut res = vec![];

        Self::traversal(&root, &mut res);

        res
    }

    fn traversal(root: &Option<Rc<RefCell<TreeNode>>>, res: &mut Vec<i32>) {
        if let Some(node) = root {
            let node = node.borrow();

            Self::traversal(&node.left, res);
            Self::traversal(&node.right, res);
            res.push(node.val);
        }
    }
}

代码（思路二）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut result = vec![];
        let mut stack = vec![];
        
        if let Some(node) = root {
            stack.push(node);
        }
        
        while let Some(node) = stack.pop() {
            // 1. 访问当前节点 中
            let node_ref = node.borrow();
            result.push(node_ref.val);
            
            // 2. 左子节点后入栈（后处理）左
            if let Some(left) = &node_ref.left {
                stack.push(left.clone());
            }

            // 3. 右子节点先入栈（先处理）右
            if let Some(right) = &node_ref.right {
                stack.push(right.clone());
            }
        }

        // 中 右 左 -> 反转 左 右 中
        result.into_iter().rev().collect()
    }
}

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

inorder_1.jpg

1
2
输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

1
2
输入：root = []
输出：[]

示例 3：

1
2
输入：root = [1]
输出：[1]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

💡 思路：

  1. 递归法
  2. 迭代法

代码（思路一）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut res = vec![];

        Self::traversal(&root, &mut res);

        res
    }

    fn traversal(root: &Option<Rc<RefCell<TreeNode>>>, vec: &mut Vec<i32>) {
        if let Some(node) = root {
            let node = node.borrow();

            Self::traversal(&node.left, vec);
            vec.push(node.val);
            Self::traversal(&node.right, vec);
        }
    }
}

代码（思路二）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut result = vec![];
        let mut stack = vec![];
        let mut current = root;
    
        // 循环条件：当前节点非空或栈非空
        while current.is_some() || !stack.is_empty() {
            // 1. 深入左子树到底部，沿途压栈
            while let Some(node) = current {
                stack.push(Rc::clone(&node));
                current = node.borrow().left.as_ref().map(Rc::clone);
            }
    
            // 2. 弹出栈顶节点并访问
            if let Some(node) = stack.pop() {
                result.push(node.borrow().val);
                // 3. 转向右子树
                current = node.borrow().right.as_ref().map(Rc::clone);
            }
        }
    
        result
    }
}

统一迭代模板遍历二叉树

上方前中后序迭代法代码实现可见：模板不统一

其实也可以用统一模板实现，前面模板不同意是因为无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。

💡 思路：将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。

  1. 方法一：就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法可以叫做空指针标记法。
  2. 方法二：加一个 boolean 值跟随每个节点，false (默认值) 表示需要为该节点和它的左右儿子安排在栈中的位次，true 表示该节点的位次之前已经安排过了，可以收割节点了。 这种方法可以叫做boolean 标记法。

代码（空指针标记法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
use std::rc::Rc;
use std::cell::RefCell;
impl Solution{
    // 前序
    pub fn preorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut res = vec![];
        let mut stack = vec![];
        if root.is_some(){
            stack.push(root);
        }
        while !stack.is_empty(){
            if let Some(node) = stack.pop().unwrap(){
                if node.borrow().right.is_some(){
                    stack.push(node.borrow().right.clone());
                }
                if node.borrow().left.is_some(){
                    stack.push(node.borrow().left.clone());
                }
                stack.push(Some(node));
                stack.push(None);
            }else{
                res.push(stack.pop().unwrap().unwrap().borrow().val);
            }
        }
        res
    }
    // 中序
    pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut res = vec![];
        let mut stack = vec![];
        if root.is_some() {
            stack.push(root);
        }
        while !stack.is_empty() {
            if let Some(node) = stack.pop().unwrap() {
                if node.borrow().right.is_some() {
                    stack.push(node.borrow().right.clone());
                }
                stack.push(Some(node.clone()));
                stack.push(None);
                if node.borrow().left.is_some() {
                    stack.push(node.borrow().left.clone());
                }
            } else {
                res.push(stack.pop().unwrap().unwrap().borrow().val);
            }
        }
        res
    }
    // 后序
    pub fn postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut res = vec![];
        let mut stack = vec![];
        if root.is_some() {
            stack.push(root);
        }
        while !stack.is_empty() {
            if let Some(node) = stack.pop().unwrap() {
                stack.push(Some(node.clone()));
                stack.push(None);
                if node.borrow().right.is_some() {
                    stack.push(node.borrow().right.clone());
                }
                if node.borrow().left.is_some() {
                    stack.push(node.borrow().left.clone());
                }
            } else {
                res.push(stack.pop().unwrap().unwrap().borrow().val);
            }
        }
        res
    }
}

代码（boolean标记法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut res = vec![];
        let mut stack = vec![(root, false)];

				// 后序遍历
        while let Some((node, visited)) = stack.pop() {
            if let Some(node) = node {
                if visited {
                    res.push(node.borrow().val);
                } else {
                    stack.push((Some(node.clone()), true)); // 中
                    stack.push((node.borrow().right.clone(), false)); // 右
                    stack.push((node.borrow().left.clone(), false)); // 左
                }
            }
        }
        res
    }
    
    pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut res = vec![];
        let mut stack = vec![(root, false)];

				// 中序遍历
        while let Some((node, visited)) = stack.pop() {
            if let Some(node) = node {
                if visited {
                    res.push(node.borrow().val);
                } else {
		                stack.push((node.borrow().right.clone(), false)); // 右
                    stack.push((Some(node.clone()), true)); // 中
                    stack.push((node.borrow().left.clone(), false)); // 左
                }
            }
        }
        res
    }
    
    pub fn postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut res = vec![];
        let mut stack = vec![(root, false)];

				// 前序遍历
        while let Some((node, visited)) = stack.pop() {
            if let Some(node) = node {
                if visited {
                    res.push(node.borrow().val);
                } else {
		                stack.push((node.borrow().right.clone(), false)); // 右
		                stack.push((node.borrow().left.clone(), false)); // 左
                    stack.push((Some(node.clone()), true)); // 中
                }
            }
        }
        res
}

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

tree1.jpg

1
2
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

1
2
输入：root = [1]
输出：[[1]]

示例 3：

1
2
输入：root = []
输出：[]

提示：

  • 树中节点数目在范围 [0, 2000] 内
  • -1000 <= Node.val <= 1000

💡 思路：
层序遍历二叉树是指从左到右、一层一层地遍历整个树结构。
这种遍历需要借助队列这个辅助数据结构来实现。队列的先进先出特性完美契合了逐层遍历的需求，而栈的先进后出特性则更适合实现深度优先的递归遍历。
本质上，这种层序遍历就是图论中广度优先遍历在二叉树上的应用。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;
impl Solution {
    pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
        let mut ans = vec![];
        let mut queue = VecDeque::new();

        if let Some(node) = root {
            queue.push_back(node); // 头节点入队列
        }

        while !queue.is_empty() {
            let level_size = queue.len(); // 队列长度 即 该层的节点数
            let mut level_values = vec![]; // 存放该层节点
						
						// 循环弹出当前层节点，并将该层子节点如队列
            for _ in 0..level_size {
                let node = queue.pop_front().unwrap();
                let node_ref = node.borrow();
                
                level_values.push(node_ref.val); // 记录该层节点
                
                if let Some(left) = &node_ref.left {
                    queue.push_back(left.clone());
                }
                if let Some(right) = &node_ref.right {
                    queue.push_back(right.clone());
                }
            }
            
            // 保存结果
            ans.push(level_values);
        }

        ans
    }
}

代码（递归实现）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
        let mut result = Vec::new();
        Self::traverse(root.as_ref(), 0, &mut result);
        result
    }

    fn traverse(
        node: Option<&Rc<RefCell<TreeNode>>>,
        level: usize,
        result: &mut Vec<Vec<i32>>,
    ) {
        if let Some(n) = node {
            // 确保结果数组有足够的层级
            if result.len() == level {
                result.push(Vec::new());
            }
            
            let node_ref = n.borrow();
            // 将当前节点值存入对应层级
            result[level].push(node_ref.val);
            
            // 递归处理左右子树，level+1
            Self::traverse(node_ref.left.as_ref(), level + 1, result);
            Self::traverse(node_ref.right.as_ref(), level + 1, result);
        }
    }
}

107. 二叉树的层序遍历 II

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例 1：

tree1.jpg

1
2
输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

示例 2：

1
2
输入：root = [1]
输出：[[1]]

示例 3：

1
2
输入：root = []
输出：[]

提示：

  • 树中节点数目在范围 [0, 2000] 内
  • -1000 <= Node.val <= 1000

💡 思路：相较于102. 二叉树的层序遍历，最后将结果反转一下就行

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;
impl Solution {
    pub fn level_order_bottom(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
        let mut ans = vec![];
        let mut queue = VecDeque::new();

        if let Some(node) = root {
            queue.push_back(node); // 头节点入队列
        }

        while !queue.is_empty() {
            let level_size = queue.len(); // 队列长度 即 该层的节点数
            let mut level_values = vec![]; // 存放该层节点
						
						// 循环弹出当前层节点，并将该层子节点如队列
            for _ in 0..level_size {
                let node = queue.pop_front().unwrap();
                let node_ref = node.borrow();
                
                level_values.push(node_ref.val); // 记录该层节点
                
                if let Some(left) = &node_ref.left {
                    queue.push_back(left.clone());
                }
                if let Some(right) = &node_ref.right {
                    queue.push_back(right.clone());
                }
            }
            
            // 保存结果
            ans.push(level_values);
        }

        ans.reverse();
        ans
    }
}

199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1：

输入：root = [1,2,3,null,5,null,4]

输出：[1,3,4]

解释：

tmpd5jn43fs-1.png

示例 2：

输入：root = [1,2,3,4,null,null,null,5]

输出：[1,3,4,5]

解释：

tmpkpe40xeh-1.png

示例 3：

输入：root = [1,null,3]

输出：[1,3]

示例 4：

输入：root = []

输出：[]

提示:

  • 二叉树的节点个数的范围是 [0,100]
  • -100 <= Node.val <= 100

💡 思路：将层序遍历最后一个节点放入结果集中即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;
impl Solution {
    pub fn right_side_view(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut ans = vec![];
        let mut queue = VecDeque::new();

        if let Some(node) = root {
            queue.push_back(node);
        }

        while !queue.is_empty() {
            let level = queue.len();

            for i in 0..level {
                let node = queue.pop_front().unwrap();
                let node_ref = node.borrow();

                if i == level - 1 {
                    ans.push(node_ref.val);
                }

                if let Some(left) = &node_ref.left {
                    queue.push_back(left.clone());
                }

                if let Some(right) = &node_ref.right {
                    queue.push_back(right.clone());
                }
            }
        }

        ans
    }
}

637. 二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10^-5 以内的答案可以被接受。

示例 1：

avg1-tree.jpg

1
2
3
4
输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。

示例 2:

avg2-tree.jpg

1
2
输入：root = [3,9,20,15,7]
输出：[3.00000,14.50000,11.00000]

提示：

  • 树中节点数量在 [1, 10^4] 范围内
  • -2^31 <= Node.val <= 2^31 - 1

💡 思路：层序遍历，每层计算总和，后求平均值放入结果集

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;
impl Solution {
    pub fn average_of_levels(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<f64> {
        let mut ans = Vec::new();
        let mut queue = VecDeque::new();

        root.map(|node| queue.push_back(node));

        while !queue.is_empty() {
            let level_size = queue.len();
            let mut sum = 0i64;

            for _ in 0..level_size {
                let node = queue.pop_front().unwrap();
                let node_ref = node.borrow();
                
                sum += node_ref.val as i64;

                if let Some(left) = node_ref.left.as_ref() {
                    queue.push_back(Rc::clone(left));
                }
                if let Some(right) = node_ref.right.as_ref() {
                    queue.push_back(Rc::clone(right));
                }
            }

            ans.push(sum as f64 / level_size as f64);
        }

        ans
    }
}

429. N 叉树的层序遍历

给定一个 N 叉树，返回其节点值的_层序遍历_。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：

narytreeexample.png

1
2
输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]

示例 2：

sample_4_964.png

1
2
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

提示：

  • 树的高度不会超过 1000
  • 树的节点总数在 [0, 10^4] 之间

💡 思路：同层序遍历

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#[derive(Debug, PartialEq, Eq)]
pub struct Node {
    pub val: i32,
    pub children: Vec<Option<Rc<RefCell<Node>>>>,
}

impl Node {
    #[inline]
    pub fn new(val: i32) -> Node {
        Node {
            val,
            children: vec![],
        }
    }
}

use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;
impl Solution {
    pub fn level_order(root: Option<Rc<RefCell<Node>>>) -> Vec<Vec<i32>> {
        let mut res = vec![];
        let mut queue = VecDeque::new();
        if let Some(root) = root {
            queue.push_back(root);
        }
        while !queue.is_empty() {
            let mut temp = vec![];
            for _ in 0..queue.len() {
                let node = queue.pop_front().unwrap();
                temp.push(node.borrow().val);
                for child in &node.borrow().children {
                    if let Some(child) = child {
                        queue.push_back(child.clone());
                    }
                }
            }
            res.push(temp);
        }
        res
    }
}

515. 在每个树行中找最大值

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例1：

largest_e1.jpg

1
2
输入:root = [1,3,2,5,3,null,9]
输出:[1,3,9]

示例2：

1
2
输入:root = [1,2,3]
输出:[1,3]

提示：

  • 二叉树的节点个数的范围是 [0,10^4]
  • -2^31 <= Node.val <= 2^31 - 1

💡 思路：层序遍历，每层获取max

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;
impl Solution {
    pub fn largest_values(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut ans = vec![];
        let mut queue = VecDeque::new();

        if let Some(node) = root {
            queue.push_back(node);
        }

        while !queue.is_empty() {
            // 用当前层第一个节点初始化max
            let mut max = queue.front().unwrap().borrow().val;
            for _ in 0..queue.len() {
                let node = queue.pop_front().unwrap();
                let node_ref = node.borrow();

                max = node_ref.val.max(max);

                if let Some(left) = &node_ref.left {
                    queue.push_back(left.clone());
                }

                if let Some(right) = &node_ref.right {
                    queue.push_back(right.clone());
                }
            }

            ans.push(max);
        }

        ans
    }
}

104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

tmp-tree.jpg

1
2
输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

1
2
输入：root = [1,null,2]
输出：2

提示：

  • 树中节点的数量在 [0, 10^4] 区间内。
  • -100 <= Node.val <= 100

💡 思路：层序遍历，记录层数就行

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;
impl Solution {
    pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut queue = VecDeque::new();

        if let Some(node) = root {
            queue.push_back(node);
        }

        let mut depth = 0;
        while !queue.is_empty() {
            depth += 1;
            for _ in 0..queue.len() {
                let node = queue.pop_front().unwrap();
                let node_ref = node.borrow();

                if let Some(left) = &node_ref.left {
                    queue.push_back(left.clone());
                }

                if let Some(right) = &node_ref.right {
                    queue.push_back(right.clone());
                }
            }
        }

        depth
    }
}

此外，用递归实现也是十分方便的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 node_ref = node.borrow();
                let left_depth = Self::max_depth(node_ref.left.clone());
                let right_depth = Self::max_depth(node_ref.right.clone());
                1 + left_depth.max(right_depth)
            }
        }
    }
}

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：

ex_depth.jpg

1
2
输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

1
2
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

  • 树中节点数的范围在 [0, 10^5] 内
  • -1000 <= Node.val <= 1000

💡 思路：同层序遍历，每遍历一层，层数+1，当遇到一个节点同时没有左右孩子时，提前返回

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;
impl Solution {
    pub fn min_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        match root {
            Some(node) => {
                let mut res = 0;
                let mut queue = VecDeque::new();
                queue.push_back(node);
                while !queue.is_empty() {
                    res += 1;
                    for _ in 0..queue.len() {
                        let node = queue.pop_front().unwrap();
                        let node = node.borrow();
                        if node.left.is_none() && node.right.is_none() {
                            return res;
                        }
                        if let Some(node) = node.left.clone() {
                            queue.push_back(node);
                        }
                        if let Some(node) = node.right.clone() {
                            queue.push_back(node);
                        }
                    }
                }
                res
            }
            None => 0,
        }
    }
}

递归法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn min_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        match root {
            None => 0,
            Some(node) => {
                let node_ref = node.borrow();
                let left_depth = Self::min_depth(node_ref.left.clone());
                let right_depth = Self::min_depth(node_ref.right.clone());
                
                // 只有当左右子树都存在时才取最小值
                if left_depth == 0 || right_depth == 0 {
                    1 + left_depth + right_depth
                } else {
		                // 当左右子树都存在时，最小深度自然是左右子树最小深度的较小值加1
                    1 + left_depth.min(right_depth)
                }
            }
        }
    }
}