【Day 13 】2021-09-22 - 104. 二叉树的最大深度

[azl397985856]

104. 二叉树的最大深度

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree

前置知识

• 递归

  题目描述

  
  给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例： 给定二叉树 [3,9,20,null,null,15,7]，

3

/ \ 9 20 / \ 15 7 返回它的最大深度 3 。

[yiwchen]

直接法：

Python:

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root == None:
            return 0
        else:
            return max(self.maxDepth(root.left),self.maxDepth(root.right))+1

新工作可能要java，改行用java刷了（ Java:

class Solution {
  public int maxDepth(TreeNode root) {
    if (root == null) {
      return 0;
    } else {
      return java.lang.Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
  }
}

TC: O(n) visiting all nodes SC: O(h) calling stack

[joriscai]

思路

• 使用广度优先遍历
• 在遍历时，进入下一层，深度+1，
• 然后整一层遍历，一层遍历完后，重新进入下一层，重复到队列为空

  代码

  javascript

/**
 * 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) {
  const queue = []
  if (root) queue.push(root)
  let depth = 0
  while (queue.length) {
    depth++
    const len = queue.length
    for (let i = 0; i < len; i++) {
      // 边删除边判断是否有下一层
      const node = queue.shift()
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
  }
  return depth
};

复杂度分析

• 时间复杂度：O(n)，每一层全部节点都要判断一下是否有下一层节点
• 空间复杂度：O(n)，最大的时候，空间占用是n个节点

[xbhog]

104. 二叉树的最大深度

思路：

先不要思考太多，老板的思想，当前节点，找到左节点的最大深度，找到右节点的最大深度，两者取最大值，再加上本身。

Java代码段：

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left,right)+1;
    }
}

复杂度分析：

时间复杂度：O(n)

空间复杂度：O(height)

[learning-go123]

思路

• dfs递归求最大值

代码

• 语言支持：Go

Go Code:

/**
 * 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
    }
    return max(maxDepth(root.Left) + 1, maxDepth(root.Right) + 1)
}

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

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[ychen8777]

思路

就 递归

代码

class Solution {
    public int maxDepth(TreeNode root) {

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

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

    }
}

复杂度

时间: O(n) \ 空间: O(n)

[wangyifan2018]

/**
 * 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
    }
    return 1 + max(maxDepth(root.Right), maxDepth(root.Left))
}

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

复杂度分析

时间复杂度： O(n)

空间复杂度： O(height)

[skinnyh]

Note

Use recursion. The max depth is 1+max(left, right)

Solution

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

Time complexity: O(N)

Space complexity: O(h) worst case O(N) when the tree is a list

[akxuan]

DFS

time: O(depth) memory: O(N)

    def maxDepth(self, root):
        if not root:          return 0 
        return max( self.maxDepth(root.left) ,self.maxDepth(root.right))+1

[HouHao1998]

思想

递归

代码

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

复杂度

T：O（N） S：O（H）树的深度

[xiezhengyun]

思路

递归

/**
 * 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
  var left = maxDepth(root.left)
  var right = maxDepth(root.right)
  return Math.max(left, right) + 1
};

复杂度

N是树的元素个数，H是树高度（递归所用）

• Time O(N)
• Space O(H)

[joeytor]

思路

递归遍历整棵树, 每次return是返回 max(left, right) + 1, 即返回左/右子树最深的数 + 1为 root 节点的深度

代码

# 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 not root:
            return 0

        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)

        return max(left, right) + 1

复杂度

时间复杂度: O(n) n为节点数, 因为会访问每个节点

空间复杂度: O(n) n为节点数, 因为最差会退化成链表, 所以递归栈的深度是n

[Cartie-ZhouMo]

思路

递归遍历，返回 max(left, right) + 1

代码

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

复杂度

• 时间：O(N) 节点数
• 空间：O(n) 深度

[liuyangqiQAQ]

简单题，放大假。

class Solution {
    public int maxDepth(TreeNode root) {
        //深度优先还是广度优先？看心情
        //dfs
        return dfs(root);
    }
    public int dfs(TreeNode node) {
        if(node != null) {
            return Math.max(dfs(node.left), dfs(node.right)) + 1;
        }
        return 0;
    }
}

复杂度分析

时间复杂度:O(N) 遍历每一个节点。故N为节点数量 空间复杂度:O(M) 递归遍历占用的栈空间为树的高度。

[shamworld]

思路

递归遍历

代码

var maxDepth = function(root) {
    if(!root) return 0;
    if(!root.left&&!root.right) return 1;
    return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
};

复杂度分析:

• 时间复杂度:O(n)
• 空间复杂度:O(n)

[aatoe]

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(!root) return 0
    return Math.max( maxDepth(root.left),maxDepth(root.right) ) + 1
};

时间复杂度 O(N)，原因是因为只走了递归的算法，然后每一个递归分开后，需要把这层调用栈的速度合在一起，所以是O(N)。
空间复杂度：O(h)，其中 h 为树的深度，最坏的情况 h 等于 N，其中 N 为节点数，此时树退化到链表。

[Master-guang]

每日一题：104.二叉树的最大深度 (2021.9.22)

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

语言：JavaScript

思路

• 递归
• 终止条件：当前节点为空 返回值：节点为空时说明高度为 0，所以返回 0；节点不为空时则分别求左右子树的高度的最大值，同时加1表示当前节点的高度，返回该数值

代码

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

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[kendj-staff]

z

class Solution {
    public int maxDepth(TreeNode root) {
        return findMax(root);
    }
    public int findMax (TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(findMax(root.left) + 1, findMax(root.right) + 1);
    }

[KennethAlgol]

思路

深度优先搜索 如果我们知道了左子树和右子树的最大深度 ll 和 rr，那么该二叉树的最大深度即为 max(l,r)+1

语言

java

/**
 * 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;
        }else{
            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);
            return Math.max(leftHeight,rightHeight) + 1;
        }
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。

空间复杂度：O(height)，其中 height 表示二叉树的高度。

[JK1452470209]

思路

dfs考虑选取最深深度

代码

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
    }
}

复杂度

时间复杂度：O(N)

空间复杂度：O(N)

[xieyj17]

# 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: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        m_left = self.maxDepth(root.left) + 1
        m_right = self.maxDepth(root.right) + 1
        return max(m_left, m_right)

Time: O(N)

Space: O(N)

[juleijs]

思路

递归

代码

const maxDepth = root => {
  return root ? Math.max(maxDepth(root.left), maxDepth(root.right)) + 1 : 0;
}

复杂度

• 时间复杂度：O(N)
• 空间复杂度：O(N)

[flame0409]

class Solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; } else { int leftHeight = maxDepth(root.left); int rightHeight = maxDepth(root.right); return Math.max(leftHeight, rightHeight) + 1; } } }

[wenlong201807]

解题思路

最大高度可能来源
1. 根结点都没有，那么高度就没有，未0 或者null
2. 有根结点时，最大高度可能在左子树中，也可能在右子树上
3. 也可能左子树的右子树上，也可能右子树的左子树上
4. 递归解决吧，还没完全唔到

代码块

var maxDepth = function(root) {
  if (!root) return root;

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

时间复杂度和空间复杂度

• 时间复杂度 O(n*n)
• 空间复杂度 O(n)

[james20141606]

Day 13 104. Maximum Depth of Binary Tree (binary tree, BFS)

• Problem Link

  • 104. Maximum Depth of Binary Tree

• Ideas

  • it is an easy problem. We just focus on the basic structure, focus on one root and use recursion to solve the problem.

• Complexity:

  • Time: O(# nodes)
  • Space: O(depth of the tree) (worst case are #nodes(which degenerates to linked list))

• Code

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        return 1 + max( maxDepth(root.left) + maxDepth(root.right))

• other resources:

[lilixikun]

思路

• 递归分别遍历左右子树、然后求出来最大的

  代码

  var maxDepth = function(root) {
  if(root==null){
       return 0
  }
  return 1+ Math.max(maxDepth(root.left),maxDepth(root.right))
  }

  迭代

  相比递归、我觉得递归其实更容易理解、就是一层一层的累加下去、看树的高度

  代码

  var maxDepth = function(root) {
  if(!root){
      return 0
  }
  const stack = [root]
  let maxDepth = 0
  while(stack.length){
      let len = stack.length
      while(len--){
          const node = stack.shift()
          if(node.left){
              stack.push(node.left)
          }
          if(node.right){
              stack.push(node.right)
          }
      }
      maxDepth++
  }
  return maxDepth
  };

[user1689]

题目

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

思路

DFS, BFS

python

# 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:

        def dfs(root):
            if not root: 
                return 0
            if not root.left and not root.right:
                return 1

            maxDepth = max(dfs(root.left), dfs(root.right)) + 1
            return maxDepth

        return dfs(root)

# 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
import queue
class Solution:
# 写法二
    def maxDepth(self, root: TreeNode) -> int:
        # time n
        # space height
        # 思路二
        # BFS
        if not root: return 0

        q = deque()
        q.append(root)
        step = 0
        while q:
            size = len(q)
            for _ in range(size):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            step += 1

        return step

复杂度分析

• time n
• space height/logn

相关题目

1. https://leetcode-cn.com/problems/balanced-binary-tree/
2. https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
3. https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree/

[chakochako]

class Solution:
    def maxDepth(self, root):
        if root is None: 
            return 0 
        else: 
            left_height = self.maxDepth(root.left) 
            right_height = self.maxDepth(root.right) 
            return max(left_height, right_height) + 1 

[iambigchen]

思路

利用递归，计算出left和right最大路径后，加1就是该点的最大路径。

代码

var maxDepth = function(root) {
    if (root === null) {
        return 0
    } else {
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
    }

};

复杂度

时间复杂度 O(N)

空间复杂度 O(n) n为树的深度

[itsjacob]

Intuition

• The maximum depth of the tree can only be available after traversing all the nodes in the tree, therefore dfs/bfs gives the same time complexity, which is O(n).
• The simplest solution is recursion, which is equavilent to the dfs approach.
• Using bfs approach, we can save O(n) space queue for storing the depth information on each node, because we have depth information on each level

Implementation

/**
 * 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 == nullptr) return 0;
    // dfs approach
    std::stack<TreeNode *> theNodeStack;
    std::queue<int> theDepthQueue;
    theNodeStack.push(root);
    theDepthQueue.push(1);
    int maxDepth{ 0 };
    while (!theNodeStack.empty()) {
      TreeNode *subroot = theNodeStack.top();
      theNodeStack.pop();
      int curDepth = theDepthQueue.front();
      theDepthQueue.pop();
      maxDepth = std::max(maxDepth, curDepth);
      if (subroot->left != nullptr) {
        theNodeStack.push(subroot->left);
        theDepthQueue.push(curDepth + 1);
      }
      if (subroot->right != nullptr) {
        theNodeStack.push(subroot->right);
        theDepthQueue.push(curDepth + 1);
      }
    }
    return maxDepth;
  }
};

Complexity

• Time complexity: O(n) for traversing the tree
• Space complexity: O(logN) for storing the nodes on stack

[Dana-Dai]

递归实现

class Solution {
public:
    int maxDepth(TreeNode* root) {
        //确定递归终止条件
        if (root == nullptr) return 0;

        //确定单层递归的逻辑
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);
        int midDepth = 1 + max(leftDepth, rightDepth);

        return midDepth;
    }
};

层序遍历（队列）

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        queue<TreeNode*> que;
        int ans = 0;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            ans ++;
            for (int i = size - 1; i >= 0; i --) {
                TreeNode* cur = que.front();
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        }
        return ans;
    }
};

时间复杂度：O(n)

[Francis-xsc]

思路

递归求左右子树高度的较大值

代码

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root)
            return 0;
        int l=maxDepth(root->left),r=maxDepth(root->right);
        return (l>r?l:r)+1;
    }
};

复杂度分析

• 时间复杂度：O(N)，其中 N 为结点个数。
• 空间复杂度：O(1)

[ruohai0925]

题目地址()

题目描述

前置知识

公司

• 暂无

思路

关键点

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    """
    @param root: The root of binary tree.
    @return: An integer
    """

    def maxDepth(self, root):

        if root is None:
            return 0

        if root.left == None:
            return self.maxDepth(root.right) + 1
        if root.right == None:
            return self.maxDepth(root.left) + 1

        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(h)$

[jsu-arch]

思路

Recursion 最底层返回0 每往上一个就是node 的左边或右边+1

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
            if root is None:
                return 0

            return max(self.maxDepth(root.left), self.maxDepth(root.right))+1

Time Complexity: O(n). Traverse every single node once.

Space Complexity: O(log(n)). There will be log(n) levels.

[Daniel-Zheng]

思路

DFS。

代码(C++)

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

复杂度分析

• 时间复杂度：O(N)，N为二叉树节点数量。
• 空间复杂度：O(M)，M为二叉树高度。

[laofuWF]

💻Code:

# recursion: post order traversal
# currNode max depth = max(leftNodeMax, rightNodeMax) + 1
# time: O(N)
# space: O(M), depth of the tree
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root: return 0

        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)

        currMax = max(left, right) + 1

        return currMax

[YQYCS]

思路

深度优先遍历

代码

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        else:
            return max(self.maxDepth(root.left),self.maxDepth(root.right)) + 1

复杂度

时间复杂度：O(n)。 空间复杂度：O(height)。

[ai2095]

LC104. Maximum Depth of Binary Tree

https://leetcode.com/problems/maximum-depth-of-binary-tree/

Topics

• Tree

Similar Questions

Easy

• https://leetcode.com/problems/minimum-depth-of-binary-tree/

Medium

• https://leetcode.com/problems/time-needed-to-inform-all-employees/

思路

Recursion

代码 Python

# 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: Optional[TreeNode]) -> int:
        if not root:
            return 0

        def findDepth(root):
            if not root:
                return 0

            leftDepth = findDepth(root.left)
            rightDepth = findDepth(root.right)

            return 1 + max(leftDepth, rightDepth)

        return findDepth(root)

复杂度分析

时间复杂度：O(N)
空间复杂度：O(N)

[SunStrongChina]

104. 二叉树的最大深度

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree

前置知识

• 递归

题目描述

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

  3
 / \
9  20
  /  \
 15   7
返回它的最大深度 3 。

DFS,最大深度等于max(左子树最大深度,右子树最大深度)+1

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right))+1

时间复杂度：O(N) 空间复杂度:O(logn)

BFS 解法，此种解法就是一直往队列中加入节点，然后一层一层计算，层序遍历，计算树最多有多少层

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        #迭代解法，层序遍历解此题
        q=deque()
        q.append(root)
        lenth1=0
        while q:
            size1=len(q)
            for i in range(size1):
                if i==size1-1:
                    lenth1+=1
                r1=q.popleft()
                if r1.left:
                    q.append(r1.left)
                if  r1.right:
                    q.append(r1.right)
        return lenth1

时间复杂度：O(N) 空间复杂度: O(N)

[naomiwufzz]

思路1：dfs

深度优先搜索，输入是节点，输出是当前root的最大深度；实现逻辑是当前节点的最大深度是左节点最大深度和右节点最大深度的max；出口是当前节点是none

代码

# 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:
        # 返回当前节点的最大深度
        # 出口：非节点
        # 逻辑：计算root的最大深度，一个root的深度是左右深度最大
        def dfs(node):
            if not node:
                return 0
            depth = max(dfs(node.left), dfs(node.right))
            return depth + 1
        return dfs(root)

复杂度分析

• 时间复杂度：O(n) 每个节点遍历一次
• 空间复杂度：O(h) 递归栈的栈空间是树的深度

思路2：bfs

层序遍历，每一层深度加一

代码

# 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
from collections import deque
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        # bfs
        queue = deque()
        if not root:
            return 0
        queue.append(root)
        depth = 0
        while queue:
            for i in range(len(queue)):
                cur_node = queue.popleft()
                if cur_node.left:
                    queue.append(cur_node.left)
                if cur_node.right:
                    queue.append(cur_node.right)
            depth += 1
        return depth

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n) 最大是队列存储的最多的节点，最坏情况是O(n)

[zhousibao]

function maxDepth(root: TreeNode | null): number {
    function getDeep(node:TreeNode | null){
        if(node === null){
            return 0
        }
        const left = getDeep(node.left)
        const right = getDeep(node.right)

        return left >= right ? left + 1 : right + 1
    }
    return getDeep(root)
};

[Zhang6260]

JAVA版本

思路：方法一，使用dfs

​ 方法二，进行层次遍历

方法一:

class Solution {

public int maxDepth(TreeNode root) {

​ if(root==null)return 0;

​ int a=maxDepth(root.left)+1;

​ int b=maxDepth(root.right)+1

​ return Math.max(a,b);

}

}

时间复杂度：O(n)

空间复杂度：O(M)(树的高度)

方法二：

class Solution {

int max=0;

public int maxDepth(TreeNode root) {

​ if(root==null)return 0;

​ Queue queue = new LinkedList<>();

​ queue.offer(root);

​ TreeNode node=null;

​ int res=0;

​ while(!queue.isEmpty()){

​ int size=queue.size();

​ while(size>0){

​ node=queue.poll();

​ if(node.left!=null){

​ queue.offer(node.left);

​ }

​ if(node.right!=null){

​ queue.offer(node.right);

​ }

​ size--;

​ }

​ res++;

​ }

​ return res;

}

时间复杂度：O(N)

空间复杂度：O(N)

[MonkofEast]

104. Maximum Depth of Binary Tree

Click Me

Algo

1. Return max(dep(left), dep(right))
2. stop when entered an empty node at last

Code

# 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: Optional[TreeNode]) -> int:
        if not root: return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

Comp

T: O(N)

S: O(depth)

[laurallalala]

代码

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

复杂度

• 时间复杂度：O(N)
• 空间复杂度：O(H)

[Zz10044]

class Solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; } else { int leftHeight = maxDepth(root.left); int rightHeight = maxDepth(root.right); return Math.max(leftHeight, rightHeight) + 1; } } }

[watermelonDrip]

# 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 not root:
            return 0
        def dfs(node):
            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            return max(left,right) + 1
        return max(dfs(root.left),dfs(root.right))+1

时间复杂度：O(n) 空间复杂的：O(1)

[last-Battle]

思路

关键点

• 分治

代码

• 语言支持：C++

C++ Code:

/**
 * 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 == nullptr) {
            return 0;
        }

        auto left = maxDepth(root->left);
        auto right = maxDepth(root->right);

        return 1 + max(left, right);
    }
};

复杂度分析

令 n 为树的节点个数。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

[yan0327]

思路： 利用二叉树的后续遍历，实现DFS。当左子树右子树均为nil时，记录栈的最大值为最大深度

func maxDepth(root *TreeNode) int {
    out := 0
    stack := []*TreeNode{}
    var pre *TreeNode
    for root != nil || len(stack) > 0{
        for root != nil{
            stack = append(stack, root)
            out = max(out, len(stack))
            root = root.Left
        }
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if root.Right == nil || root.Right == pre{
            out = max(out, len(stack))
            pre = root
            root = nil
        }else{
            stack = append(stack, root)
            root = root.Right
        }
    }
    return out
}

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

时间复杂度：O(N) 空间复杂度：O（M）M为二叉树的最大深度

[suukii]

Link to LeetCode Problem

S1: DFS

先计算出左子树和右子树的高度，取两者中的最大值，加上当前节点 1，就是当前二叉树的最大深度。

递归出口：

• 空节点
• 叶子节点

/**
 * 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 == nullptr) return 0;
        if (root->left == nullptr && root->right == nullptr) return 1;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

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

# 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

• Time: $O(N)$，N 是二叉树的节点总数。
• Space: $O(logN)$，递归栈的空间，最坏的情况是二叉树退化成了链表，那递归栈的深度就成了 $O(N)$。

S2: BFS

前置：

102. 二叉树的层序遍历

也可用 BFS 的方式来遍历二叉树，每遍历一层深度就加一，再用一个全局变量来追踪深度最大值即可。

/**
 * 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) {
        int maxD = 0;
        depth(root, 0, maxD);
        return maxD;
    }
    void depth(TreeNode* root, int curD, int& maxD) {
        if (root == nullptr) {
            maxD = max(maxD, curD);
            return;
        }
        depth(root->left, curD + 1, maxD);
        depth(root->right, curD + 1, maxD);
    }
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
    if (!root) return 0;

    let height = 0;
    const queue = [root];

    while (queue.length) {
        let len = queue.length;
        height++;

        while (len > 0) {
            const node = queue.shift();
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
            len--;
        }
    }

    return height;
};

# 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
        """
        queue = []
        if root is not None: queue.append(root)
        height = 0

        while True:
            nodeCount = len(queue)
            if nodeCount == 0: return height
            height += 1

            while nodeCount > 0:
                node = queue.pop(0)
                if node.left is not None: queue.append(node.left)
                if node.right is not None: queue.append(node.right)
                nodeCount -= 1

• Time: $O(N)$，N 是二叉树的节点总数。
• Space: $O(logN)$，队列或者递归栈的空间，最坏的情况是二叉树退化成了链表，那空间就成了 $O(N)$。

[siyuelee]

Recursion

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

O(n) O(depth)

[ysy0707]

思路: DFS与BFS

//dfs
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        } else {
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);
            return Math.max(left, right) + 1;
        }
    }
}

//BFS
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        // 若当前节点为null 则返回0
        }

        int maxDepth = 0;

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        // 将根节点放入队列

        while (!queue.isEmpty()){
            maxDepth += 1;
            // 遍历队列中的元素，队列不为空，则最大深度加1

            int cueLevelNum = queue.size();
             // 计算当前这一层有多少个节点
            for(int i = 0; i < cueLevelNum; i++ ){
                // for循环是遍历当前这一层的所有节点
                TreeNode curNode = queue.removeFirst();
                if(curNode.left != null) {
                    queue.add(curNode.left);
                }
                if(curNode.right != null) {
                    queue.add(curNode.right);
            // 同时如果其左子树或右子树不为空，则将其加入队列,等待下一while循环
                }
            }
        }
        return maxDepth;
    }
}

时间复杂度：O(N) 空间复杂度：O(N)