二叉树的最大深度计算

题解思路

本题需要求二叉树的最大深度，即从根节点到最远叶子节点的最长路径上的节点数。
解题的核心思路是树的遍历+递归计算深度，可以使用深度优先搜索（DFS） 或 广度优先搜索（BFS） 来求解。

方法

1. 深度优先搜索（DFS）递归法

• 递归计算左右子树的最大深度，然后取最大值加1（根节点）。
• 递归终止条件：遇到 null 节点时，返回深度 0。
• 递归公式： $depth(root) =$$\max(depth(root.left), depth(root.right)) + 1$
• 适用于深度较小的二叉树，时间复杂度 $O(n)$，空间复杂度 $O(h)$（$h$ 为树的高度，最坏 $O(n)$）。

2. 广度优先搜索（BFS）迭代法

• 使用队列按层遍历二叉树，每遍历完一层，深度加1。
• 适用于树较深时，避免递归带来的栈溢出问题。
• 时间复杂度 $O(n)$，空间复杂度 $O(n)$。

算法复杂度分析

• 时间复杂度：$O(n)$，因为每个节点都访问一次。
• 空间复杂度：
  • DFS（递归）：最坏情况下 $O(n)$（退化成链表）。
  • BFS（迭代）：$O(n)$（队列存储所有叶子节点）。

代码实现

Python 代码

# 定义二叉树节点类
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val       # 节点值
        self.left = left     # 左子树
        self.right = right   # 右子树

def build_tree(level_order):
    if not level_order or level_order[0] == 'null':
        return None
    
    root = TreeNode(int(level_order[0]))
    queue = [root]
    i = 1
    while i < len(level_order):
        current = queue.pop(0)
        # 构造左子节点
        if i < len(level_order) and level_order[i] != 'null':
            current.left = TreeNode(int(level_order[i]))
            queue.append(current.left)
        i += 1
        # 构造右子节点
        if i < len(level_order) and level_order[i] != 'null':
            current.right = TreeNode(int(level_order[i]))
            queue.append(current.right)
        i += 1
    return root

def max_depth(root):
    """
    递归计算二叉树的最大深度
    :param root: 二叉树的根节点
    :return: 最大深度
    """
    if root is None:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

if __name__ == "__main__":
    import sys
    # 读取输入数据
    input_data = sys.stdin.read().strip()
    tokens = input_data.split()
    # 构造二叉树
    root = build_tree(tokens)
    # 输出二叉树的最大深度
    print(max_depth(root))

Java 代码

import java.util.*;

// 定义二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

public class Main {
    // 根据层次遍历构造二叉树
    public static TreeNode buildTree(String[] tokens) {
        if (tokens.length == 0 || tokens[0].equals("null"))
            return null;
        
        TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int i = 1;
        while (i < tokens.length) {
            TreeNode current = queue.poll();
            // 构造左子节点
            if (i < tokens.length && !tokens[i].equals("null")) {
                current.left = new TreeNode(Integer.parseInt(tokens[i]));
                queue.offer(current.left);
            }
            i++;
            // 构造右子节点
            if (i < tokens.length && !tokens[i].equals("null")) {
                current.right = new TreeNode(Integer.parseInt(tokens[i]));
                queue.offer(current.right);
            }
            i++;
        }
        return root;
    }
    
    // 递归计算二叉树的最大深度
    public static int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<String> tokensList = new ArrayList<>();
        // 按空格读取所有输入数据
        while (scanner.hasNext()) {
            tokensList.add(scanner.next());
        }
        scanner.close();
        String[] tokens = tokensList.toArray(new String[0]);
        TreeNode root = buildTree(tokens);
        System.out.println(maxDepth(root));
    }
}

C++ 代码

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

// 定义二叉树节点结构体
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

// 根据层次遍历结果构造二叉树
TreeNode* buildTree(const vector<string>& tokens) {
    if (tokens.empty() || tokens[0] == "null")
        return nullptr;
    
    TreeNode* root = new TreeNode(stoi(tokens[0]));
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (i < tokens.size()) {
        TreeNode* current = q.front();
        q.pop();
        // 构造左子节点
        if (i < tokens.size() && tokens[i] != "null") {
            current->left = new TreeNode(stoi(tokens[i]));
            q.push(current->left);
        }
        i++;
        // 构造右子节点
        if (i < tokens.size() && tokens[i] != "null") {
            current->right = new TreeNode(stoi(tokens[i]));
            q.push(current->right);
        }
        i++;
    }
    return root;
}

// 递归计算二叉树的最大深度
int maxDepth(TreeNode* root) {
    if (root == nullptr)
        return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string input;
    getline(cin, input);
    istringstream iss(input);
    vector<string> tokens;
    string token;
    while (iss >> token) {
        tokens.push_back(token);
    }
    
    TreeNode* root = buildTree(tokens);
    cout << maxDepth(root);
    
    return 0;
}

题目内容

给定一个二叉树 $root$，输出其最大深度。

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

输入描述

一行包含二叉树的序列化数组，节点值之间用空格隔开，空节点用null表示。

输出描述

一个整数，表示最大深度。

样例1

输入

3 9 20 null null 15 7

输出

3

样例2

输入

1 null 2

输出

2

提示

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