104. Maximum Depth of Binary Tree

Question

LeetCode Problem

Image: View on LeetCode

Given the root of a binary tree, return its maximum depth .
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Example 1:

Input: root = [3,9,20,null,null,15,7] Output: 3

Example 2:

Input: root = [1,null,2] Output: 2

Constraints:

• The number of nodes in the tree is in the range [0, 10 4 ] .
• -100 <= Node.val <= 100

Solutions

Use recursion. This approach is not good for interview because it is too easy. ⚠️

int maxDepth(TreeNode* root) {
	if (root == nullptr) return 0;
	int leftDepth = maxDepth(root->left) + 1;
	int rightDepth = maxDepth(root->right) + 1;
	return max(leftDepth, rightDepth);
}

Use iteration with BFS (w/ queue). This approach is good for interview because it can prevent from stack overflow.

int maxDepth(TreeNode* root) {
	if (root == nullptr) return 0;
	queue<TreeNode*> q;
	q.push(root);
	int depthNum = 0;
	while (!q.empty()) {
		size_t levelNum = q.size();
		for (int i = 0; i < levelNum; ++i) {
			TreeNode* node = q.front();
			q.pop();
			if (node->left) q.push(node->left);
			if (node->right) q.push(node->right);
		}
		depthNum += 1;
	}
	return depthNum;
}