二叉树的深度、路径总和、将有序数组转换为二叉搜索树、二叉搜索树迭代器（2022/02/23）

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    # 深度优先搜索
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        
        leftHeight = self.maxDepth(root.left)
        rightHeight = self.maxDepth(root.right)
        return max(leftHeight, rightHeight) + 1
    #  广度优先搜索
    def maxDepth(self, root: Optional[TreeNode]) -> int:  
        if not root:
            return 0
        queue = [root]
        res = 0
        while queue:
            size = len(queue)
            for _ in range(size):
                curr = queue.pop(0)
                if curr.left:
                    queue.append(curr.left)
                if curr.right:
                    queue.append(curr.right)
            res +=1
        return res

# 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:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        # 递归求解
        return self.sum(root, targetSum, 0)
    def sum(self, root:TreeNode, targetSum:int, currSum:int):
        if root == None:
            return False
        
        curSum += root.val
        if root.left == None and root.right == None:
            return currSum == targetSum
        else:
            return self.sum(root.left, targetSum, currSum) or self.sum(root.right, targetSum, currSum)
# 广度优先搜索进行遍历
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        queue = [root]
        queue_val = [root.val]
        while queue:
            now = queue.pop(0)
            temp = queue_val.pop(0)
            if not now.left and not now.right:
                if temp == targetSum:
                    return True
                continue
            if now.left:
                queue.append(now.left)
                queue_val.append(now.left.val + temp )
            if now.right:
                queue.append(now.right)
                queue_val.append(now.right.val + temp)
        return False

# 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:
    # 方法一：深度优先搜索
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        if not root.left and not root.right:
            return 1
        
        min_depth = 10**9
        if root.left:
            min_depth = min(self.minDepth(root.left), min_depth)
        if root.right:
            min_depth = min(self.minDepth(root.right), min_depth)
        return min_depth + 1
# 方法二：广度优先搜索
    import collections
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        que = collections.deque([(root,1)])
        while que:
            node, depth = que.popleft()
            if not node.left and not node.right:
                return depth
            
            if node.left:
                que.append((node.left, depth + 1))
            
            if node.right:
                que.append((node.right, depth + 1))
        return 0

# 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:
    # 方法一：中序遍历，总是选择中间位置左边的数字作为根节点
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def helper(left, right):
            if left > right:
                return None
            mid = (left + right) // 2
            root = TreeNode(nums[mid])
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root
        return helper(0, len(nums) - 1)
    # 方法二：中序遍历，总是选择中间位置右边的数字作为根节点
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def helper(left, right):
            if left >right:
                return None
            mid = (left + right + 1) //2
            root = TreeNode(nums[mid])
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root
        return helper(0, len(nums) - 1)
    # 方法三：中序遍历，选择任意一个中间位置数字作为根节点
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def helper(left, right):
            if left > right:
                return None
            # 选择任意一个中间位置数字作为根节点
            mid = (left + right + randint(0, 1)) // 2
            root = TreeNode(nums[mid])
            root.left = helper(left, mid - 1)
            root.right = helper(mid + 1, right)
            return root
        return helper(0, len(nums) - 1)

# 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 BSTIterator:
    def __init__(self, root: TreeNode):
        self.stack = []
        self.in_order(root)
    def next(self) -> int:
        node = self.stack.pop()
        if node.right:
            self.in_order(node.right)
        return node.val
    def in_order(self, node):
        while node:
            self.stack.append(node)
            node = node.left
    def hasNext(self) -> bool:
        return len(self.stack) != 0        
# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()