时间轴

2025-10-23

init

题目：

P104 二叉树的最大深度

https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150

递归

一颗二叉树的最大深度等于它左子树的最大深度和右子树最大深度的最大值+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL){
            return 0;
        }
        if(root->left==NULL && root->right==NULL){
            return 1;
        }
        return std::max(maxDepth(root->left)+1, maxDepth(root->right)+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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode()
		: val(0)
		, left(nullptr)
		, right(nullptr)
	{
	}
	TreeNode(int x)
		: val(x)
		, left(nullptr)
		, right(nullptr)
	{
	}
	TreeNode(int x, TreeNode *left, TreeNode *right)
		: val(x)
		, left(left)
		, right(right)
	{
	}
};
#include <queue>

class Solution {
    public:
	int maxDepth(TreeNode *root)
	{
		if (root == NULL) {
			return 0;
		}
		// 层次遍历求最大深度
		int depth = 1;
		std::queue<TreeNode *> que;

		TreeNode *tmp;
		int i, qsize;
		que.push(root);

		while (!que.empty()) {
			qsize = que.size();
			for (i = 0; i < qsize; i++) {
				tmp = que.front();
				que.pop();
				if (tmp->left != NULL) {
					que.push(tmp->left);
				}
				if (tmp->right != NULL) {
					que.push(tmp->right);
				}
			}
			depth++;
		}
		return depth;
	}
};

rust实现

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
use std::cell::RefCell;
use std::rc::Rc;

// 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,
        }
    }
}
struct Solution;

use std::collections::VecDeque;

impl Solution {
    pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut depth = 0_i32;
        let mut length = 0;
        let mut que = VecDeque::new();

        if let Some(root) = root {
            que.push_back(root);
        } else {
            return 0;
        }

        while !que.is_empty() {
            length = que.len();
            for _ in 0..length {
                if let Some(node) = que.front() {
                    let node = Rc::clone(node); 
                    let node_ref = node.borrow();

                    // 先处理再 pop_front
                    if let Some(left) = &node_ref.left {
                        que.push_back(Rc::clone(left));
                    }
                    if let Some(right) = &node_ref.right {
                        que.push_back(Rc::clone(right));
                    }

                    
                    que.pop_front();
                }
            }

            depth += 1;
        }
        depth
    }
}
fn main() {}