集团网站源码,wordpress主题 下单,网站建设 源码,做物流的网站有哪些功能二叉树的直径 题目题解解释 题目
543. 二叉树的直径
给你一棵二叉树的根节点#xff0c;返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
题解
… 二叉树的直径 题目题解解释 题目
543. 二叉树的直径
给你一棵二叉树的根节点返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
题解
思路找到左边最长和右边最长
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution(object):def diameterOfBinaryTree(self, root)::type root: Optional[TreeNode]:rtype: intself.ans 0def dfs(root):if root is None:return -1l_len dfs(root.left) 1r_len dfs(root.right) 1self.ans max(self.ans, l_len r_len)return max(l_len, r_len)dfs(root)return self.ans 解释
假设我们有以下的二叉树 1/ \2 3/ \ 4 5步骤 1: 初始调用 diameterOfBinaryTree(root) 调用 dfs(root)即传入根节点 1。
步骤 2: 递归计算深度 对节点 1 左子树递归调用 dfs(root.left)即节点 2。 对节点 2 左子树递归调用 dfs(root.left)即节点 4。 节点 4 是叶子节点因此返回 0。 右子树递归调用 dfs(root.right)即节点 5。 节点 5 是叶子节点因此返回 0。 对节点 2l_len 0 1 1r_len 0 1 1self.ans max(0, 1 1) 2返回 max(1, 1) 1。 对节点 1 左子树返回节点 2 的深度 1。 右子树递归调用 dfs(root.right)即节点 3。 节点 3 是叶子节点因此返回 0。 对节点 1l_len 1 1 2r_len 0 1 1self.ans max(2, 2 1) 3返回 max(2, 1) 2。
步骤 3: 返回结果 最终返回 self.ans 3表示二叉树的直径为 3即从节点 4 到节点 5通过节点 2 再到节点 1该路径包含 3 个节点。
