104. Depth of binary tree

Difficulty: simple
Given a binary tree, find its maximum depth.
The depth of the binary tree is the number of nodes on the longest path from the root node to the farthest leaf node.
Note: leaf nodes refer to nodes without child nodes.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
Returns its maximum depth 3.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    # Depth first search
    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

    #  Breadth first search
    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

112. Path sum

Difficulty: simple
Give you the root node of the binary tree root and an integer targetSum representing the target sum. Judge whether there is a path from the root node to the leaf node in the tree. The sum of all node values on this path is equal to the target and targetSum. If it exists, return true; Otherwise, false is returned.
A leaf node is a node that has no child nodes.

Example 1: input: root = [5,4,8,11, null, 13,4,7,2, null, null, 1], targetsum = 22
Output: true explanation: the path from the root node to the leaf node equal to the target sum is shown in the figure above.
Example 2: input: root = [1,2,3], targetSum
=5 Output: false explanation: there are two paths from root node to leaf node in the tree: (1 -- > 2): and 3 (1 -- > 3): and 4. There is no path from root node to leaf node with sum = 5.
Example 3: input: root = [], targetSum = 0, output: false
Explanation: since the tree is empty, there is no path from root node to leaf node.

# 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:
        # Recursive solution
        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)

# Breadth first search for traversal

    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

111. Minimum depth of binary tree

Difficulty: simple
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes on the shortest path from the root node to the nearest leaf node.
Note: leaf nodes refer to nodes without child nodes.
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 2
Example 2:
Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

# 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:
    # Method 1: depth first search
    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

# Method 2: breadth first search
    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

108. Convert the ordered array into a binary search tree

Difficulty: simple
Give you an integer array nums, in which the elements have been arranged in ascending order. Please convert it into a highly balanced binary search tree.
A height balanced binary tree is a binary tree that satisfies the requirement that the absolute value of the height difference between the left and right subtrees of each node does not exceed 1.
Example 1:
Input: num = [- 10, - 3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] will also be regarded as the correct answer:
Example 2:
Input: num = [1,3]
Output: [3,1]
Explanation: [1,3] and [3,1] are highly balanced binary search trees.
Tips:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
Strictly in ascending order of nums

# 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:
    # Method 1: middle order traversal, always select the number on the left of the middle position as the root node
    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)

    # Method 2: middle order traversal, always select the number on the right of the middle position as the root node

    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)

    # Method 3: middle order traversal, select any middle position number as the root node
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def helper(left, right):
            if left > right:
                return None

            # Select any number in the middle as the root node
            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)

173. Binary search tree iterator

Difficulty: medium
Implement a binary search tree iterator class BSTIterator, which represents an iterator that traverses the binary search tree (BST) in medium order:
BSTIterator(TreeNode root) initializes an object of the BSTIterator class. The root node of BST is given as part of the constructor. The pointer should be initialized to a number that does not exist in the BST and is less than any element in the BST.
boolean hasNext() returns true if there is a number traversing to the right of the pointer; Otherwise, false is returned.
int next() moves the pointer to the right and returns the number at the pointer.
Note that the pointer is initialized to a number that does not exist in the BST, so the first call to next() will return the smallest element in the BST.
You can assume that the next() call is always valid, that is, when next() is called, there is at least one next number in the middle order traversal of BST.
Example:
input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
output
[null, 3, 7, true, 9, true, 15, true, 20, false]
explain
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // Return 3
bSTIterator.next(); // Return to 7
bSTIterator.hasNext(); // Return True
bSTIterator.next(); // Return to 9
bSTIterator.hasNext(); // Return True
bSTIterator.next(); // Return to 15
bSTIterator.hasNext(); // Return True
bSTIterator.next(); // Return to 20
bSTIterator.hasNext(); // Return False
Tips:
The number of nodes in the tree is in the range [1, 105]
0 <= Node.val <= 106
Call up to 105 hasNext and next operations
Advanced:
Can you design a solution that meets the following conditions? The next() and hasNext() operations share the time complexity of O(1) and use O(h) memory. Where h is the height of the tree.

# 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()