543 二叉树的直径（递归-搜索每个根节点的最大直径）

秒速五厘米 2022-08-31 02:30 110阅读 0赞

**1. 问题描述：**

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

**示例 :**

给定二叉树  
1  
/ \\  
2 3  
/ \\  
4 5  
返回 3, 它的长度是路径 \[4,2,1,3\] 或者 \[5,2,1,3\]。  
注意：两结点之间的路径长度是以它们之间边的数目表示。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/diameter-of-binary-tree

**2. 思路分析：**

分析题目可以知道我们需要求解出二叉树的最大直径，因为是二叉树所以最简单的求解方法是求解每一个以当前的节点为根节点的最大直径，我们可以分别**递归**当前节点的左子树与右子树，分别求解出左右子树的最大路径，左右子树的最大路径相加就是当前节点为根的最大直径，在递归的时候我们需要维一个全局变量res作为当前二叉树的最大直径。

**3. 代码如下：**

# class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    
    
    class Solution:
        # 维护当前二叉树的最大直径
        res = 0
    
        def dfs(self, root: TreeNode):
            if not root: return 0
            # 左子树的最大路径
            l = self.dfs(root.left)
            # 右子树的最大路径
            r = self.dfs(root.right)
            self.res = max(self.res, l + r)
            # 返回当前节点的最大路径注意需要加1
            return max(l, r) + 1
    
        def diameterOfBinaryTree(self, root: TreeNode) -> int:
            self.dfs(root)
            return self.res