Interview Classic 150 Problem P104: Maximum Depth of Binary Tree

---

Timeline

Timeline

2025-10-23

init

Find the maximum depth of a binary tree using recursion or level-order traversal

---

Problem:

P104 Maximum Depth of Binary Tree

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

Recursion

The maximum depth of a binary tree equals the maximum of the maximum depths of its left and right subtrees, plus 1.

/**
 * 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);
    }
};

Level-order traversal

In level-order traversal, remember the number of nodes in each level each time

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;
		}
		// Find maximum depth using level-order traversal
		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 implementation

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();

                    // Process first, then 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() {}

leetcode hot 100 rewrite

/**
 * 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) {}
 * };
 */

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 <algorithm>
class Solution {
    public:
        int maxDepth(TreeNode *root)
        {
                if (root == nullptr)
                        return 0;

                return std::max(maxDepth(root->left), maxDepth(root->right)) + 1;
        }
};