二叉树的直径

描述

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

      1
     / \
    2   3
   / \     
  4   5    

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/diameter-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

这里使用了递归的方法来解决这个问题。对于每个节点，我们需要计算它的左子树和右子树的深度，并更新直径。在递归过程中，我们可以同时计算当前子树的深度，这样就不需要再次遍历整个树来计算深度了。

具体来说，我们定义一个 dfs 函数来进行递归。这个函数接受一个树节点 root 和一个整数引用 diameter，表示当前已经计算出的直径。如果 root 为空，说明当前节点是一个空节点，直接返回深度 0。否则，我们递归计算左子树和右子树的深度，并更新直径。最后，返回当前子树的深度，即左子树深度和右子树深度的较大值加上 1。

在 diameterOfBinaryTree 函数中，我们调用 dfs 函数来计算直径，并返回结果。

C++代码

/**
 * 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 {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int diameter = 0;
        dfs(root, diameter);
        return diameter;
    }
    
    int dfs(TreeNode* root, int& diameter) {
        if (!root) {
            return 0;
        }
        // 计算左子树的深度
        int left_depth = dfs(root->left, diameter);
        // 计算右子树的深度
        int right_depth = dfs(root->right, diameter);
        // 更新直径
        diameter = max(diameter, left_depth + right_depth);
        // 返回当前子树的深度
        return max(left_depth, right_depth) + 1;
    }
};

Python代码

class Solution:
    def __init__(self):
        self.maxDiameter = 0

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.maxDepth(root)
        return self.maxDiameter
        
    def maxDepth(self, root):
        if not root:
            return 0
        leftMax = self.maxDepth(root.left)
        rightMax = self.maxDepth(root.right)
        self.maxDiameter = max(self.maxDiameter, leftMax + rightMax)
        return max(leftMax, rightMax) + 1