Python, Simple with Explanation


  • 12

    Let's calculate the depth of a node in the usual way: max(depth of node.left, depth of node.right) + 1. While we do, a path "through" this node uses 1 + (depth of node.left) + (depth of node.right) nodes. Let's search each node and remember the highest number of nodes used in some path. The desired length is 1 minus this number.

    def diameterOfBinaryTree(self, root):
        self.best = 1
        def depth(root):
            if not root: return 0
            ansL = depth(root.left)
            ansR = depth(root.right)
            self.best = max(self.best, ansL + ansR + 1)
            return 1 + max(ansL, ansR)
            
        depth(root)
        return self.best - 1
    

  • 4
    T

    Great solution!
    Just one doubt, why do you add and substract self.best by 1?

    This seems to me more readable:

    self.best = 0
    def depth(root):
        ...
        self.best = max(self.best, ansL + ansR)
        ...
    ...
    return self.best
    

  • 0
    Y

    Re: [Python](Simple with Explanation)

    I think it is conceptually clearer to add 2 and no subtract.

    class Solution(object):
        def diameterOfBinaryTree(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            self.best = 0
            def dfs(node):
                if not node:
                    return -1
                left = dfs(node.left)
                right = dfs(node.right)
                self.best = max(self.best, left + right + 2)
                return max(left, right) + 1
            
            dfs(root)
            return self.best
    

  • 0
    C

    @yuez1989 yeah! but we add two only when the node has both left and right child, in case of only one child we add one only.

     def diameterOfBinaryTree(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            self.dim = 0
            def lpath(node):
                if node is None:
                    return 0
                if node.left is None and node.right is None:
                    return 0
                l = lpath(node.left)
                r = lpath(node.right)
                if node.left is not None and node.right is not None:
                    self.dim = max(self.dim,l+r+2)
                else:
                    self.dim = max(self.dim,l+r+1)
                return max(l,r)+1;
            lpath(root)
            return self.dim
    

  • 0
    A

    @awice why we subtract by 1 at the end?


  • 0
    A

    @awice what is the time complexity?


Log in to reply
 

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