543.Diameter of Binary Tree

Tags: [recursion], [tree], [binary_tree], [extend_meaning]

Com: {fb}

Link: https://leetcode.com/problems/diameter-of-binary-tree/\#/description

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of thelongestpath between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

          1
         / \
        2   3
       / \     
      4   5

Return3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

Solution: Extend Meaning

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

class Solution(object):
    def diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        diameter, _ = self.diameter_helper(root)
        return diameter

    def diameter_helper(self, root):
        # base case
        if not root or (not root.left and not root.right):
            return 0, 0

        left_diameter, left_longest_path = self.diameter_helper(root.left)
        right_diameter, right_longest_path = self.diameter_helper(root.right)

        path = 0
        if root.left:
            path += 1 + left_longest_path
        if root.right:
            path += 1 + right_longest_path

        return (max(path, left_diameter, right_diameter), 
                max(left_longest_path, right_longest_path) + 1)

Revelation:

• Extend the function meaning.
• Check whether root.left is None or not, to decide whether path += 1 + left_longest_path, the reason we check root.left, not checking left_longest_path, is that the root.left maybe a leaf node, the left_longest_path = 0, but the path need plus 1, because there exist one edge between root and root.left. The same thing for the root.right.

Note:

• Time complexity = O(n), n is the number of nodes of the given tree, because each node we only visit once.
• Space complexity = O(h), h is the height of the given tree, because we do recursion, the max depth of recursion is the height of the given tree.