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