543. Diameter of Binary Tree 🔥

Easy

Problem:

Return the length of the longest path between two nodes in a binary tree.

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].

https://leetcode.com/problems/diameter-of-binary-tree/

Solution:

DFS

First, search down to the furthest leaf nodes, and then ascend back up, updating each node's longest path and depth value. If the node is None, the function returns -1. This is because, in this solution, the depth of a leaf node is considered 0, and since there's no edge from a leaf node to its non-existent child, it returns -1.

Updating Longest Path:

For each node, the potential longest path that passes through it is left + right + 2. This is because the path includes the left depth, the right depth, and the two edges connecting the current node to its left and right children.
The global longest variable keeps track of the longest path found so far. It's updated with max(self.longest, left + right + 2) to ensure it always contains the maximum value.

Returning Depth:

After calculating the potential longest path for the current node, the function needs to return its depth to its parent. The depth of the current node is 1 (the edge to its deepest child) plus the depth of its deepest child. This is given by max(left, right) + 1.

# 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:
    longest: int = 0
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def dfs(node: TreeNode) -> int:
            if not node:
                return -1
            # Search to the leaf nodes
            left = dfs(node.left)
            right = dfs(node.right)

            # longest path
            self.longest = max(self.longest, left + right + 2)
            # status
            return max(left, right) + 1
        
        dfs(root)
        return self.longest

When reassigning a parent function's variable inside a nested function, the reference ID changes and it's declared as a separate local variable. If the value of 'longest' is not a number or string but a data type like a list or dictionary, it can be manipulated without reassignment using methods like append(). However, since numbers and strings are immutable objects, their values cannot be changed within the nested function. Therefore, longest has been set as a class variable.

Last updated 2 years ago