Welcome to Subscribe On Youtube

104. Maximum Depth of Binary Tree

Description

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, 104].
• -100 <= Node.val <= 100

Solutions

Solution 1: Recursion

Recursively traverse the left and right subtrees, calculate the maximum depth of the left and right subtrees, and then take the maximum value plus $1$.

The time complexity is $O(n)$, where $n$ is the number of nodes in the binary tree. Each node is traversed only once in the recursion.

• Java
• C++
• Python
• Go
• TypeScript
• Javascript
• RenderScript

• /**
   * 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);
      }
  }
  

• /**
   * Definition for a binary tree node.
   * struct TreeNode {
   *     int val;
   *     TreeNode *left;
   *     TreeNode *right;
   *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
   *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
   *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
   * };
   */
  class Solution {
  public:
      int maxDepth(TreeNode* root) {
          if (!root) return 0;
          int l = maxDepth(root->left), r = maxDepth(root->right);
          return 1 + max(l, r);
      }
  };
  

• # 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.
   * 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)
  }
  

• /**
   * 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)
      }
  }
  
  

All Problems

All Solutions