Python - Postorder Traversal Method


  • 0
    U

    This method is a postorder traversal method. The children of the root will calculate it's longest path and its height of the subtree, and the longest path of the whole tree will be the max among (right_subtree_longest, left_subtree_longest, longest_path_through_root).

    def diameterOfBinaryTree(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            def helper(root):
                """
                input: root of a tree
                output: (longest path, height)
                """
                if root is None:
                    return 0, 0
                if root.left is None and root.right is None:
                    return 0, 0
                left = helper(root.left)
                right = helper(root.right)
                longest_root_path = 0
                if root.left:
                    longest_root_path += left[1] + 1
                if root.right:
                    longest_root_path += right[1] + 1
                longest_path = max(left[0], right[0], longest_root_path)
                height = max(left[1], right[1]) + 1
                return (longest_path, height)
                
            return helper(root)[0]
    

Log in to reply
 

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