西安专业网站建设服务,wordpress 标签鼠标滑过_弹出的title 代码美化,建网站用什么软件,html5做网站链接题目描述#xff1a; 给你一棵二叉树的根节点#xff0c;返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。
示例 1#xff1a; 输入#xff1a;ro…题目描述 给你一棵二叉树的根节点返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。
示例 1 输入root [1,2,3,4,5] 输出3 解释3 取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2 输入root [1,2] 输出1
思路 对于该节点的左儿子向下遍历经过最多的节点数 L 即以左儿子为根的子树的深度 和其右儿子向下遍历经过最多的节点数 R 即以右儿子为根的子树的深度那么以该节点为起点的路径经过节点数的最大值即为 LR1。
算法流程 定义一个递归函数 depth(node) 计算 node函数返回该节点为根的子树的深度。先递归调用左儿子和右儿子求得它们为根的子树的深度 L 和 R 则该节点为根的子树的深度即为max(L,R)1该节点的node值为LR1。
递归搜索每个节点并设一个全局变量 ans记录node的最大值最后返回 ans-1 即为树的直径。
python
class Solution:def diameterOfBinaryTree(self, root: TreeNode) - int:# 初始化节点数为1self.ans 1def depth(node):# 访问到空节点了返回0if not node:return 0# 左儿子为根的子树的深度L depth(node.left)# 右儿子为根的子树的深度R depth(node.right)# 计算d_node即LR1 并更新ansself.ans max(self.ans, L R 1)# 返回该节点为根的子树的深度return max(L, R) 1depth(root)return self.ans - 1
