How to optimize it further? Two traversals


  • 0
    S

    I know it seems like a bad solution but its most natural one, how can I prevent double traversals - one of for height and another for diameter?

    class Solution(object):
        def __init__(self):
            # a sort of variable to retain across recursive call
            # records diameter of tree recorded so far
            self.diameter = 0
    
        def diameterOfBinaryTree(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            def height(root):
                if root:
                    return 1 + max( height(root.left) , height(root.right) )
                return 0
            
            if root:
                # a diameter of tree for a node is basically sum of height of left subtree and height of right subtree
                # find diameter of subtree rooted in left, and in right
                self.diameterOfBinaryTree(root.left)
                self.diameterOfBinaryTree(root.right)
                # find height of left subtree and right subtree
                left  = height(root.left)
                right =  height(root.right)
                # diameter of a tree rooted at root is sum of left subtree's height and sum of right subtree's height
                # self.diameter is a diameter of whole tree which is maximum diameter found so far
                self.diameter = max(self.diameter, left + right)
            
            return self.diameter

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.