트리에 대한 흔한 프로그래밍 문제

두 갈래 나무와 가장 큰 경로 얻기 [leetcode124] 두 갈래 나무는 노드마다 하나의 수를 가지고 가장 큰 경로를 구한다.주의: 이것은 모든 경로입니다. 한 잎 노드에서 다른 잎 노드로 가는 경로를 포함합니다..

def recursion(root, m):
    if root is None:
        return 0
    left = recursion(root.left, m)
    right = recursion(root.right, m)
    ret = max(left, right, 0) + root.val
    m[0] = max(m[0], ret, left+right+root.val)
    return ret

def maxPathSum(root):
    if root is None:
        return 0
    m = [root.val]
    recursion(root, m)
    return m[0]

두 갈래 나무의 최소 깊이와 최대 깊이[leetcode111,104]

#  
def minDepth(root):
    if root is None:
        return 0
    if root.left is not None:
        if root.right is not None:
            return min(minDepth(root.left), minDepth(root.right)) + 1
        else:
            return minDepth(root.left) + 1
    elif root.right is not None:
        return minDepth(root.right) + 1
    else:
        return 1

# 
def maxDepth(root):
    return 0 if root is None else max(maxDepth(root.left), maxDepth(root.right))+1

두 갈래 나무의 균형이 맞는지 판단하기 [leetcode110] 각 노드의 왼쪽 갈래 나무와 오른쪽 갈래 나무의 높이의 차이가 1이면 균형 두 갈래 나무..

def recursion(root, h):
    if root is None:
        h[0] = 0
        return True
    lh, rh = [0], [0]
    if not recursion(root.left, lh):
        return False
    if not recursion(root.right, rh):
        return False
    h[0] = max(lh[0], rh[0]) + 1
    return abs(lh[0] - rh[0]) <= 1

def isBalanced(root):
    return recursion(root, [0])

두 갈래 나무가 같은지 판단[leetcode100]

def isSame(root1, root2):
    if root1 is None:
        return root2 is None
    else:
        if root2 is None:
            return False
        else:
            return root1.val == root2.val and isSame(root1.left, root2.left) and isSame(root1.right, root2.right)

두 갈래 나무의 대칭 여부를 판단한다[leetcode101]

def recursion(root1, root2):
    if root1 is None:
        return root2 is None
    else:
        if root2 is None:
            return False
        else:
            return root1.val == root2.val and recursion(root1.left, root2.right) and recursion(root2.left, root1.right)

def isSymmetrical(root):
    if root is None:
        return True
    return recursion(root.left, root.right)

두 갈래 나무가 두 갈래 검색 나무인지 판단하기 [leetcode98, 173] 임의의 노드에 대해 왼쪽 나무는 그것보다 작고 오른쪽 나무는 그것보다 크다

#  ， ， 
def inorderTraversal(root, arr):
    if root is not None:
        inorderTraversal(root.left, arr)
        arr.append(root.val)
        inorderTraversal(root.right, arr)
        
def isSearchTree(root):
    arr = []
    inorderTraversal(root, arr)
    i = 1
    while i < len(arr):
        if arr[i-1] >= arr[i]:
            return False
        i += 1
    return True