543. Diameter of Binary Tree

Diameter of Binary Tree - LeetCode

1. 실패한 코드

# Definition for a binary tree node.
from typing import *
from collections import deque


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    start = None

    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        if not self.start:
            self.start = root
        if not root:
            return 0
        if not root.left and not root.right:
            if root == self.start:
                return 0
            return 1
        else:
            left = self.diameterOfBinaryTree(root.left)
            right = self.diameterOfBinaryTree(root.right)
            if self.start == root:
                return left + right
            else:
                return max(left, right) + 1

실패 테스트 케이스

[4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2]

원인

Tree DP 마냥 올라가면 안 된다. 최댓값을 반환하는 문제기 때문에 루트 노드를 거치지 않고도 답이 나올 수도 있다.

반례는 아래와 같다. (오픈 톡방 cgiosy님 반례)

2. 해법

class Solution:
    def __init__(self):
        self.result = 0

    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        def dfs(root):
            if not root:
                return 0
            left = dfs(root.left)
            right = dfs(root.right)
            self.result = max(self.result, left + right)
            return max(left, right) + 1

        dfs(root)
        return self.result

괜히 내부 함수 없이 주어진 함수 그대로 재귀로 넘기려고 했다가 문제 요구 사항을 제대로 짚지 못했다.