Skip to content

Latest commit

 

History

History
160 lines (125 loc) · 3.78 KB

104.Maximum_Depth_of_Binary_Tree.md

File metadata and controls

160 lines (125 loc) · 3.78 KB

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

  1. Maximum Depth of Binary Tree

简单

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

相关企业

  • 领英 LinkedIn|17
  • 亚马逊 Amazon|7
  • 字节跳动|6
  • 谷歌 Google|5
  • 微软 Microsoft|3

相关标签

  • Tree
  • Depth-First Search
  • Breadth-First Search
  • Binary Tree

相似题目

  • Balanced Binary Tree 简单
  • Minimum Depth of Binary Tree 简单
  • Maximum Depth of N-ary Tree 简单

solution

# 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 max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1 
/**
 * 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;
        }

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

解题思路

  • 思路
    • 这道题用DFS（深度优先搜索）来解答。我们知道，每个节点的深度与它左右子树的深度有关，且等于其左右子树最大深度值加上 1。
  • 递归设计
    • 递归条件（recursive case）: 对于当前节点root，我们求出左右子树的深度的最大值，再加1表示当前节点的深度，返回该数值，即为以root为根节点的树的最大深度。
    • 终止条件（base case）：当前节点为空时，认为树深为0。

复杂度分析

  • 时间复杂度：O(n)，其中 n是节点的数量。我们每个节点只访问一次，因此时间复杂度为 O(n)。
  • 空间复杂度：考虑到递归使用调用栈（call stack）的情况。
    • 最坏情况：树完全不平衡。例如每个节点都只有左节点，此时将递归n 次，需要保持调用栈的存储为O(n)
    • 最好情况：树完全平衡。即树的高度为 log(n)，此时空间复杂度为 O(log(n))

代码

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

        return _maxDepth(root, 1); 
    }

    public int _maxDepth(TreeNode curr, int maxDep) {
        if (curr.left == null && curr.right == null){
            return maxDep;
        }

        int leftDepth = 0;
        int rightDepth = 0;
        if (curr.left != null){
            leftDepth = _maxDepth(curr.left, maxDep + 1);
        }
        if (curr.right != null){
            rightDepth = _maxDepth(curr.right, maxDep + 1);
        }
        maxDep = leftDepth > rightDepth ? leftDepth : rightDepth;
        return maxDep;
         
    }
}

Improve

as above solution section