[Leetcode] 543. Diameter of Binary Tree

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

initial

I tried top down but I got a very large number, which means when I reached the bottom, either my return was not updating value all the way up or my impl is wrong

but this logic I solved in 백준 we just add the height of left subtree and height of right tree. But this actually is wrong?

Lets look at this case

If we just do root.left depth + root.right depth, we are gonna get 5 (2 -> 1 -> 3 -> 4 -> 6 -> 8). At first glance, this might seem correct, but there is actually a longer pathway with diameter 6 (9 -> 7 -> 5 -> 3 -> 4 -> 6 -> 8)! This is a problem for our 1st implementation since we assume the left side of the tree is involved with the diameter calculation.

i googled and found bottom-up

solution

from bottom up, the leaf nodes should first have a value of 1. so the main logic is 1+max(left_val,right_val) cuz to count child nodes.

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(node):
            nonlocal ans
            if not node:
                return 0
            left_val = dfs(node.left)
            right_val = dfs(node.right)
            ans=max(ans,left_val+right_val)
            return 1+max(left_val,right_val)
        dfs(root)
        return ans 

complexity

n time
h space where h is recursion depth