# Title Description

Given a binary tree , Find out the maximum depth .

The depth of a binary tree is the number of nodes in the longest path from the root node to the farthest leaf node .

explain :  A leaf node is a node that has no children .

Example ：
Given binary tree [3,9,20,null,null,15,7],

3
/ \
9  20
/  \
15   7

source ： Power button （LeetCode） link ：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree

# Their thinking

If we know the maximum depth of the left and right subtrees l and r, Then the maximum depth of the binary tree is max(l,r)+1

The maximum depth of left and right subtrees can be calculated in the same way . So when we calculate the maximum depth of the current binary tree , You can recursively calculate the maximum depth of its left and right subtrees , And then in O(1) Calculate the maximum depth of the current binary tree in time . Recursion exits when an empty node is accessed .

# Solution code

Complexity analysis

Time complexity ：O(n), among n Is the number of binary tree nodes . Each node is recursively traversed only once .
Spatial complexity ：O(height), among height Represents the height of the binary tree . Recursive functions require stack space , And stack space depends on the depth of recursion , So the space complexity is equivalent to the height of the binary tree .

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
return depth(root);
}

public int depth(TreeNode root) {
if(root == null) {
return 0;
}
int l = depth(root.left) + 1;
int r = depth(root.right) + 1;
return l > r ? l : r;
}
}``````

Scroll to Top