二叉树的直径题目来源：https://leetcode-cn.com/problems/diameter-of-binary-tree/题目给定一棵二叉树，你需要计算它的直径.二叉树的直径是任意两个节点之间路径长度的最大值。该路径可能通过根节点。示例：给定一棵二叉树1/\23/\45返回3，其长度为路径[4,2,1,3]或[5,2,1,3]。注意：两个节点之间的路径长度用它们之间的边数表示。这里的解题思路需要注意，二叉树的直径（最长路径）不一定能经过根节点。如下图所示：这里，求二叉树的直径就是求最长的路径。首先判断问题是否划分为子问题。二叉树路径问题其实就是选择问题：1/\231.[左]2-12.[右]3-13.[左中右],2-1-3根据上面的分析，那么现在的问题将分为：二叉树的最长路径=max{[left],[right],[leftmiddleright]}其中[left],[right],这两种情况都可以递归求解，因为叶子节点路径为0，往上走，比如2-1，长度+1，即左右节点的递归返回值+1。如果是[left,middle和右]，其实就是左+右。代码实现类Solution:defdiameterOfBinaryTree(self,root:TreeNode)->int:self.ans=0defdiameter_of_binary_tree(node,ans):#递归退出ifnotnode:return0#递归获取左右直径left_depth=diameter_of_binary_tree(node.left,self.ans)right_depth=diameter_of_binary_tree(node.right,self.ans)#左中右的情况self.ans=max(self.ans,left_depth+right_depth)#递归得到的结果返回max(left_depth,right_depth)+1diameter_of_binary_tree(root,self.ans)returnself.ans实现结果以上就是使用递归方法求解《二叉树的直径》问题的主要内容。欢迎关注微信公众号《书所集录》
