leetcode - 543. Diameter of Binary Tree
Description
Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
The length of a path between two nodes is represented by the number of edges between them.
Example 1:
Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
Example 2:
Input: root = [1,2]
Output: 1
Constraints:
The number of nodes in the tree is in the range [1, 10^4].
-100 <= Node.val <= 100
Solution
Somehow got stuck when first saw it, after several days i knew the solution…
The largest length of the diameter of a node will be: left_depth + right_depth + 1
, and then we can update the depth
of the current node as: max(left_depth, right_depth)
.
So a post-order traversal will solve the problem.
Time complexity:
o
(
n
)
o(n)
o(n)
Space complexity:
o
(
n
)
o(n)
o(n)
Code
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
node_depth = {None: 0}
stack = [(root, 0)]
res = 0
while stack:
node, status = stack.pop()
if status == 0:
stack.append((node, 1))
if node.right:
stack.append((node.right, 0))
if node.left:
stack.append((node.left, 0))
else:
res = max(res, 1 + node_depth[node.left] + node_depth[node.right])
node_depth[node] = 1 + max(node_depth[node.left], node_depth[node.right])
return res - 1
原文地址:https://blog.csdn.net/sinat_41679123/article/details/136413392
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!