https://leetcode.com/problems/balanced-binary-tree/

---

1. 코드

from typing import Optional
"""실제 제출시에는 Solution만 제출하면 된다."""

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    ans = True

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def dfs(root, depth):
            if not root:
                return depth - 1

            left = dfs(root.left, depth + 1)
            right = dfs(root.right, depth + 1)

            if abs(left - right) > 1:
                self.ans = False
            return max(left, right)

        dfs(root, 0)
        if self.ans:
            return True
        else:
            return False


# [1,2,2,3,3,null,null,4,4]
node = TreeNode(1, None, None)
node.left = TreeNode(2, None, None)
node.left.left = TreeNode(3, None, None)
node.left.left.left = TreeNode(4, None, None)
node.left.left.right = TreeNode(4, None, None)
node.left.right = TreeNode(3, None, None)
node.right = TreeNode(2, None, None)

s = Solution()
print(s.isBalanced(node))

---

2. 후기

DFS 방식으로 접근할 때 문제 접근법

• dfs(node, depth): 상태값이 루트 노드부터 리프 노드까지의 깊이라고 가정했을 때, 리프노드의 상태값이 깊이에 따라 다른 값을 가진다. 루트 -> 리프 방향으로 1씩 증가
  -> 절대적인 깊이가 필요할 때 사용

• dfs(): 모든 리프노드의 상태값은 항상 0이 된다. 리프노드까지 내려간 다음 0에서 return 값을 통해 1씩 증가하는 구조이다. 아래 코드는 루트 노드에 도달하면 가장 깊은 노드까지의 거리를 반환한다.
  -> 상대적인 깊이를 활용하는 경우 사용

"""543. Diameter of Binary Tree..."""
def dfs(node):
	if not node:
    return -1

	left = dfs(node.left)
    right = dfs(node.right)
    ...
    # 가장 깊은 상태값이 필요하기 때문에 max 사용
    # 1씩 증가하는 구조 확인할 것
    return max(left, right) + 1 

• left, right를 dfs로 받는 후위순위 구조