二叉树的直径

题目要求

给定一棵二叉树的根节点，要求计算出这棵树的直径。这里的“直径”指的是树中任意两个节点之间最长路径的长度。值得注意的是，这条最长路径不一定要通过根节点。路径长度的定义是路径上边的数量。

解题思路

要解决这个问题，我们可以利用递归的方式来遍历二叉树。对于二叉树中的每一个节点，我们可以定义一个递归函数，该函数返回以该节点为根的子树的最大深度。在递归的过程中，我们可以更新一个全局变量来记录所遇到的最长路径的长度。

具体步骤如下：

1. 初始化一个全局变量，比如命名为 maxDiameter，用于记录遇到的最长路径的长度，初始值为 0。

2. 对二叉树进行深度优先搜索（DFS），在搜索过程中，对于每个节点，计算其左子树的最大深度和右子树的最大深度。

3. 对于每个节点，其左子树的最大深度加上右子树的最大深度的和就是通过该节点的最长路径的长度（即该节点的直径）。比较并更新全局变量 maxDiameter。

4. 递归函数应该返回节点的最大深度，即其左右子树的最大深度的最大值加 1（加的 1 是因为要包括当前节点到子节点的一条边）。

5. 递归结束后，全局变量 maxDiameter 中存储的就是整棵树的直径。

6. 返回 maxDiameter 作为结果。

通过这种方式，我们可以在遍历树的同时计算出每个节点为根的子树的最大深度，并且更新全局变量来得到整棵树的直径。这个方法的时间复杂度是 O(N)，其中 N 是树中节点的数量，因为我们需要访问树中的每个节点。

Golang 版本

package main

import (
	"fmt"
)

// TreeNode is the structure for binary tree nodes.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// maxDiameter is a global variable to keep track of the maximum diameter.
var maxDiameter int

func diameterOfBinaryTree(root *TreeNode) int {
	maxDiameter = 0
	depth(root)
	return maxDiameter
}

// depth function returns the depth of the tree and updates the maxDiameter.
func depth(node *TreeNode) int {
	if node == nil {
		return 0
	}

	leftDepth := depth(node.Left)
	rightDepth := depth(node.Right)

	// Update maxDiameter at each node.
	maxDiameter = max(maxDiameter, leftDepth+rightDepth)

	// Return the depth of the tree rooted at the current node.
	return 1 + max(leftDepth, rightDepth)
}

// max function returns the maximum of two integers.
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	// Example to create a binary tree:
	//     1
	//    / \
	//   2   3
	//  / \
	// 4   5
	root := &TreeNode{Val: 1}
	root.Left = &TreeNode{Val: 2}
	root.Right = &TreeNode{Val: 3}
	root.Left.Left = &TreeNode{Val: 4}
	root.Left.Right = &TreeNode{Val: 5}

	// Call the function and print the result.
	fmt.Println("Diameter of the binary tree is:", diameterOfBinaryTree(root))
}

这段代码定义了一个二叉树节点的结构体TreeNode，并且实现了计算二叉树直径的函数diameterOfBinaryTree。在这个函数中，我们使用了一个辅助函数depth来计算树的深度，并在计算过程中更新全局变量maxDiameter来记录遇到的最大直径。最后，main函数中创建了一个示例二叉树，并调用diameterOfBinaryTree函数来计算并打印出这棵树的直径。

C++版本

#include <iostream>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
private:
    int maxDiameter = 0;

    int depth(TreeNode* node) {
        if (node == nullptr) {
            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) {
        maxDiameter = 0;
        depth(root);
        return maxDiameter;
    }
};

int main() {
    // Example to create a binary tree:
    //     1
    //    / \
    //   2   3
    //  / \
    // 4   5
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    Solution solution;
    cout << "Diameter of the binary tree is: " << solution.diameterOfBinaryTree(root) << endl;

    // Clean up memory if needed
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

这段 C++代码定义了一个二叉树节点的结构体TreeNode，并且实现了一个解决方案类Solution，其中包含了计算二叉树直径的函数diameterOfBinaryTree。在这个函数中，我们使用了一个私有成员函数depth来计算树的深度，并在计算过程中更新成员变量maxDiameter来记录遇到的最大直径。main函数中创建了一个示例二叉树，并调用diameterOfBinaryTree函数来计算并打印出这棵树的直径。最后，代码中还包含了适当的内存清理操作。

Python 版本

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.max_diameter = 0

        def depth(node):
            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

# Example usage:
if __name__ == "__main__":
    # Create a binary tree
    #     1
    #    / \
    #   2   3
    #  / \
    # 4   5
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)

    solution = Solution()
    print("Diameter of the binary tree is:", solution.diameterOfBinaryTree(root))

这段 Python 代码定义了一个二叉树节点的类TreeNode，以及一个解决方案类Solution，其中包含了计算二叉树直径的方法diameterOfBinaryTree。在这个方法中，我们使用了一个嵌套函数depth来计算树的深度，并在计算过程中更新self.max_diameter属性来记录遇到的最大直径。__main__部分创建了一个示例二叉树，并调用diameterOfBinaryTree方法来计算并打印出这棵树的直径。

Java 版本

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

class Solution {
    private int maxDiameter = 0;

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

    private int maxDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftDepth = maxDepth(node.left);
        int rightDepth = maxDepth(node.right);
        maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

public class Main {
    public static void main(String[] args) {
        // Example to create a binary tree:
        //     1
        //    / \
        //   2   3
        //  / \
        // 4   5
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        Solution solution = new Solution();
        System.out.println("Diameter of the binary tree is: " + solution.diameterOfBinaryTree(root));
    }
}

这段 Java 代码定义了一个二叉树节点的类TreeNode，以及一个解决方案类Solution，其中包含了计算二叉树直径的方法diameterOfBinaryTree。在这个方法中，我们使用了一个私有辅助方法maxDepth来计算树的深度，并在计算过程中更新maxDiameter属性来记录遇到的最大直径。Main类中的main方法创建了一个示例二叉树，并调用diameterOfBinaryTree方法来计算并打印出这棵树的直径。

Rust 版本

// 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,
        }
    }
}

use std::cell::RefCell;
use std::rc::Rc;

struct Solution;

impl Solution {
    pub fn diameter_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        fn depth(node: &Option<Rc<RefCell<TreeNode>>>, max_diameter: &mut i32) -> i32 {
            if let Some(node) = node {
                let node = node.borrow();
                let left_depth = depth(&node.left, max_diameter);
                let right_depth = depth(&node.right, max_diameter);
                *max_diameter = (*max_diameter).max(left_depth + right_depth);
                1 + left_depth.max(right_depth)
            } else {
                0
            }
        }

        let mut max_diameter = 0;
        depth(&root, &mut max_diameter);
        max_diameter
    }
}

fn main() {
    // Example to create a binary tree:
    //     1
    //    / \
    //   2   3
    //  / \
    // 4   5
    let root = Some(Rc::new(RefCell::new(TreeNode::new(1))));
    let left = Some(Rc::new(RefCell::new(TreeNode::new(2))));
    let right = Some(Rc::new(RefCell::new(TreeNode::new(3))));
    let left_left = Some(Rc::new(RefCell::new(TreeNode::new(4))));
    let left_right = Some(Rc::new(RefCell::new(TreeNode::new(5))));

    if let Some(ref root_node) = root {
        root_node.borrow_mut().left = left;
        root_node.borrow_mut().right = right;
    }

    if let Some(ref left_node) = root.as_ref().unwrap().borrow().left {
        left_node.borrow_mut().left = left_left;
        left_node.borrow_mut().right = left_right;
    }

    println!("Diameter of the binary tree is: {}", Solution::diameter_of_binary_tree(root));
}

这段 Rust 代码定义了一个二叉树节点的结构体TreeNode，以及一个解决方案结构体Solution，其中包含了计算二叉树直径的函数diameter_of_binary_tree。在这个函数中，我们使用了一个嵌套函数depth来计算树的深度，并在计算过程中更新max_diameter变量来记录遇到的最大直径。main函数中创建了一个示例二叉树，并调用diameter_of_binary_tree函数来计算并打印出这棵树的直径。

总结

上面给出了针对计算二叉树直径的解法，分别使用了不同编程语言的代码示例。这些解法都采用了递归的方式来计算二叉树的直径，通过计算树的深度并在计算过程中更新最大直径的方式来实现。每种语言的代码都定义了二叉树节点的结构，然后实现了一个解决方案类或函数来计算直径。这些解法在不同语言中的实现细节有所不同，但核心思想都是相似的，即利用递归遍历二叉树并更新最大直径的值。