二叉树的直径

解题思路

直径的计算方式

二叉树的直径 是 任意两个节点间最长路径的边数。该路径的长度等于路径上的节点数 - 1。

关键点分析

• 任意两个节点的最长路径 必定是某个节点的 左子树最深节点到右子树最深节点 之间的路径。
• 深度优先搜索（DFS） 可以帮助我们计算每个节点的左右子树最大深度。
• 更新最大直径：对于每个节点，直径等于其左子树最大深度 + 右子树最大深度。

采用深度优先搜索（DFS）

1. 递归计算每个节点的左右子树深度：

   • 叶子节点返回 0（因为叶子没有子节点）。
   • 对于非叶子节点，其 深度 = max(左子树深度, 右子树深度) + 1。

2. 维护最大直径：

   • 计算每个节点的左子树深度 + 右子树深度，更新最大直径。

复杂度分析

• 时间复杂度：$O(n)$，每个节点访问一次。
• 空间复杂度：
  • 最坏情况下（退化为链表）：$O(n)$。
  • 最好情况下（完全二叉树）：$O(\log n)$（递归栈高度）。

代码实现

Python 代码

from typing import List, Optional
import sys

# 定义二叉树结构
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def __init__(self):
        self.max_diameter = 0  # 记录最大直径

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def depth(node: Optional[TreeNode]) -> int:
            """ 计算节点的最大深度，并更新最大直径 """
            if not node:
                return 0
            left_depth = depth(node.left)   # 计算左子树深度
            right_depth = depth(node.right) # 计算右子树深度
            self.max_diameter = max(self.max_diameter, left_depth + right_depth)
            return max(left_depth, right_depth) + 1

        depth(root)
        return self.max_diameter

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

# 读取输入并计算直径
if __name__ == "__main__":
    data = sys.stdin.read().strip().split()
    root = build_tree(data)
    solution = Solution()
    print(solution.diameterOfBinaryTree(root))

Java 代码

import java.util.*;

public class Main {

    // 定义二叉树结构
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
            left = null;
            right = null;
        }
    }

    public class Solution {
        private int maxDiameter = 0;

        // 计算节点的最大深度，并更新最大直径
        private int depth(TreeNode node) {
            if (node == null) return 0;
            int leftDepth = depth(node.left);
            int rightDepth = depth(node.right);
            maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
            return Math.max(leftDepth, rightDepth) + 1;
        }

        public int diameterOfBinaryTree(TreeNode root) {
            depth(root);
            return maxDiameter;
        }
    }

    // 根据层次遍历构造二叉树
    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 void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] data = scanner.nextLine().trim().split(" ");

        // 创建 Main 和 Solution 实例
        Main main = new Main();
        Solution solution = main.new Solution();

        TreeNode root = main.buildTree(data);
        System.out.println(solution.diameterOfBinaryTree(root));
    }
}

C++ 代码

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

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

class Solution {
private:
    int maxDiameter = 0;

    // 计算节点的最大深度，并更新最大直径
    int depth(TreeNode* node) {
        if (!node) return 0;
        int leftDepth = depth(node->left);
        int rightDepth = depth(node->right);
        maxDiameter = max(maxDiameter, leftDepth + rightDepth);
        return max(leftDepth, rightDepth) + 1;
    }

public:
    int diameterOfBinaryTree(TreeNode* root) {
        depth(root);
        return maxDiameter;
    }
};

// 根据层次遍历结果构造二叉树
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 main() {
    string input;
    getline(cin, input);
    istringstream iss(input);
    vector<string> data;
    string val;

    while (iss >> val) {
        data.push_back(val);
    }

    TreeNode* root = buildTree(data);
    Solution solution;
    cout << solution.diameterOfBinaryTree(root) << endl;

    return 0;
}

题目内容

给你一棵二叉树的根节点，输出该树的直径 。

二叉树的 直径是指树中任意两个节点之间最长路径的 长度。这条路径可能经过也可能不经过根节点 $root$ 。

两节点之间路径的长度 由它们之间边数表示。

输入描述

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

输出描述

输出该二叉树的直径，即最长路径上的边数。

样例1

输入

1 2 3 4 5

输出

3

说明

$3$ ，取路径$[4,2,1,3]$ 或$[5,2,1,3]$ 的长度。

样例2

输入

1 2

输出

1

提示

• 树中节点数目在范围 $[1, 10^4]$ 内
• $-100 <= Node.val <= 100$