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

class Solution:
    def __init__(self):
        self.ret = float("-inf")

    def maxPathSum(self, root):
        def order(node):
            if not node:
                return 0
            left = order(node.left)
            right = order(node.right)
            self.ret = max(left + node.val + right, self.ret)
            cur = node.val + max(0, left, right)
            return cur if cur > 0 else 0
        order(root)
        return self.ret

def maxProfit(prices):
    p_len = len(prices)
    if p_len <= 1: return 0
    profit, in_ = 0, prices[0]
    for i in range(1, p_len):
        in_ = min(prices[i], in_)
        profit = max(profit, prices[i] - in_)
    return profit

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

def flatten(root):
    """
    Do not return anything, modify root in-place instead.
    """
    def order(node):
        if not node:
            return
        order(node.left)
        order(node.right)
        if node.left:
            next_ = node.right if node.right else None
            node.left, node.right = None, node.left
            if next_:
                cur = node.right
                while cur.right:
                    cur = cur.right
                cur.right = next_
    order(root)

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

def buildTree(preorder, inorder):
    if not preorder: return 
    root = TreeNode(preorder[0])
    root_idx = inorder.index(preorder.pop(0))
    root.left = self.buildTree(preorder[:root_idx], inorder[:root_idx])
    root.right = self.buildTree(preorder[root_idx:], inorder[root_idx + 1:])
    return root

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

def maxDepth(root):
    # dfs
    def dfs(node):
        if not node:
            return 0
        return max(dfs(node.left), dfs(node.right)) + 1
    return dfs(root) 

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

def levelOrder(root):
    if not root:
        return []
    res, cur = [], [root]
    while cur:
        tmp = []
        for _ in range(len(cur)):
            node = cur.pop(0)
            tmp.append(node.val)
            if node.left: cur.append(node.left)
            if node.right: cur.append(node.right)
        res.append(tmp)
    return res

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

def isSymmetric(root):
    def order(left, right):
        if not left and not right: return True
        if not left or not right: return False
        return left.val == right.val and order(left.left, right.right) and order(left.right, right.left)
    
    return order(root, root)

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

def isValidBST(root):
    # 前序遍历
    def order(node, lower, upper):
        if not node:
            return True

        val = node.val

        if val <= lower or val >= upper:
            return False
        
        if not order(node.left, lower, val):
            return False
        if not order(node.right, val, upper):
            return False
        
        return True

    ret = order(root, float("-inf"), float("inf"))
    return ret

def numTrees(n):
    if n <= 1:
        return 1
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1
    for i in range(2, n + 1):   # 长度
        for j in range(1, i + 1):   # 根位置
            dp[i] += dp[j - 1] * dp[i - j]
    return dp[-1]

def inorderTraversal(root):
    def order(node):
        if not node:
            return
        order(node.left)
        res.append(node.val)
        order(node.right)
    res = []
    order(root)
    return res