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)$
Space complexity: $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）！