Question

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

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⁴].
-100 <= Node.val <= 100

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

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));
	    }
	}
}

############

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int l = maxDepth(root.left);
        int r = maxDepth(root.right);
        return 1 + Math.max(l, r);
    }
}

// OJ: https://leetcode.com/problems/maximum-depth-of-binary-tree/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int maxDepth(TreeNode* root) {
        return root ? 1 + max(maxDepth(root->left), maxDepth(root->right)) : 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 maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        l, r = self.maxDepth(root.left), self.maxDepth(root.right)
        return 1 + max(l, r)

############

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
  def maxDepth(self, root):
    """
    :type root: TreeNode
    :rtype: int
    """
    if not root:
      return 0
    return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	l, r := maxDepth(root.Left), maxDepth(root.Right)
	return 1 + max(l, r)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function maxDepth(root: TreeNode | null): number {
    if (root == null) {
        return 0;
    }
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
    if (!root) return 0;
    const l = maxDepth(root.left);
    const r = maxDepth(root.right);
    return 1 + Math.max(l, r);
};

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    fn dfs(root: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
        if root.is_none() {
            return 0;
        }
        let node = root.as_ref().unwrap().borrow();
        1 + Self::dfs(&node.left).max(Self::dfs(&node.right))
    }

    pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        Self::dfs(&root)
    }
}

104 - Maximum Depth of Binary Tree

Question

Algorithm

BFS

DFS

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

BFS

DFS

Code

All Problems

All Solutions