Postorder traversal without additional dfs


  • 0
    K

    The idea is just similar to the most of solutions where the diameter is updated by leftDepth + rightDepth on every visiting nodes. Without additionally defining a dfs function, a static variable is used to keep track of the maximum depth during the postorder traversal.

    class Solution(object):
        d=0
        ans=0
        
        def diameterOfBinaryTree(self, root):
    
            if root == None: 
                self.d=0
                return self.ans
                
            self.diameterOfBinaryTree(root.right)
            rDep=self.d
            self.diameterOfBinaryTree(root.left)
    
            self.ans=max(self.ans,self.d+rDep)
            self.d=max(self.d,rDep)+1
        
            
            return self.ans
    

Log in to reply
 

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