Diameter of Binary Tree

Problem Id: 543 Difficulty: Easy Tag: Tree


Intuition

The diameter would have one key node which all other nodes in the path is in the sub-tree of this node. And it is the sum of longest path from this node to one of its left leaf and the longest path from this node to one of its right leaf.

So we could add an additional return value depth which is the longest path from this node to any one of its leaf. And the diameter could be the depth of one node's left node and the depth of right node.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        return self._dfs(root)[1]

    def _dfs(self, node):
        """
        :return: [depth, diameter]
        """
        if node is None:
            return 0, 0
        l = self._dfs(node.left)
        r = self._dfs(node.right)
        diameter = max(l[1], r[1], l[0] + r[0])
        depth = max(l[0], r[0]) + 1
        return depth, diameter