Question

Formatted question description: https://leetcode.ca/all/104.html

104	Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

@tag-tree

Algorithm

BFS

The layer sequence traverses the binary tree, and then counts the total number of layers, which is the maximum depth of the binary tree. Note that the for loop in the while loop has a trick.

You must put q.size() in the initialization, not in the judgment stop In the condition, because the size of q changes at any time, an error will occur in the stop condition.

DFS

Typical DFS.

Code

Java

import java.util.LinkedList;
import java.util.Queue;

public class Maximum_Depth_of_Binary_Tree {

	/**
	 * Definition for a binary tree node.
	 * public class TreeNode {
	 *     int val;
	 *     TreeNode left;
	 *     TreeNode right;
	 *     TreeNode(int x) { val = x; }
	 * }
	 */

    // bfs
	public class Solution_countAsMarker {
		public int maxDepth(TreeNode root) {

			if (root == null) {
				return 0;
			}

			Queue<TreeNode> q = new LinkedList<>();
			q.offer(root);

			int currentLevelCount = 1;
			int nextLevelCount = 0;

			int depth = 0;

			while (!q.isEmpty()) {
				TreeNode current = q.poll();
				currentLevelCount--;

				if (current.left != null) {
					q.offer(current.left);
					nextLevelCount++;
				}

				if (current.right != null) {
					q.offer(current.right);
					nextLevelCount++;
				}

				if (currentLevelCount == 0) {
					currentLevelCount = nextLevelCount;
					nextLevelCount = 0;
					depth++;
				}
			}

			return depth;
		}
	}

    // @note: just a bfs, counting total level
	public class Solution_iteration_nullAsMarker {
	    public int maxDepth(TreeNode root) {

	    	if (root == null) {
	    		return 0;
	    	}

	    	Queue<TreeNode> q = new LinkedList<>();
	    	q.offer(root);
	    	q.offer(null);// @note: use null as marker for end of level

	    	int depth = 0;

	    	while (!q.isEmpty()) {
	    		TreeNode current = q.poll();

	    		if (current == null) {

	    			depth++;
	    			if (!q.isEmpty()) {
	    				q.offer(null);
	    			}

	    			continue;
	    		}

	    		if (current.left != null) {
	    			q.offer(current.left);
	    		}
	    		if (current.right != null) {
	    			q.offer(current.right);
	    		}
	    	}

	    	return depth;
	    }
	}


	public class Solution_recursion {
	    public int maxDepth(TreeNode root) {

	    	if (root == null) {
	    		return 0;
	    	}

	    	if (root.left == null && root.right == null) {
	    		return 1;
	    	}

	    	return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
	    }
	}
}

All Problems

All Solutions