azl397985856 commented 2 years ago

104. 二叉树的最大深度

入选理由

暂无

题目地址

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

前置知识

递归

题目描述


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

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

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

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

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

Yongxi-Zhou commented 2 years ago

思路

root 的最大深度等于 max(左子树的最大深度，右子树的最大深度) + 1

代码

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution(object):
        def maxDepth(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if not root:
                return 0
            left = self.maxDepth(root.left)
            right = self.maxDepth(root.right)
            return max(left, right) + 1

复杂度

time O(N) space O(1)

duke-github commented 2 years ago

思路

递归 获取左右支树的长度，取较大值 
对于每个左右树 继续获取长度的较大值

复杂度

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

代码

    public int maxDepth(TreeNode root) {
    if(root == null){
    return 0;
    }
    return getHigh(0,root);
    }

    int getHigh(int high,TreeNode tree){
        if(tree==null){
            return high;
        }
        if(tree.left == null){
            return getHigh(high+1,tree.right);
        }
        if(tree.right == null){
            return getHigh(high+1,tree.left);
        }
        return Math.max(getHigh(high+1,tree.left),getHigh(high+1,tree.right));
    }

james20141606 commented 2 years ago

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 is # nodes which degenerate to a 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:

zjsuper commented 2 years ago

#dfs
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        level = 1
        ans = 1
        stack = [(root,level)]
        while stack:
            node,level = stack.pop()
            ans = max(level,ans)
            if node.left:
                stack.append((node.left,level+1))
            if node.right:
                stack.append((node.right,level+1))
        return ans

ZacheryCao commented 2 years ago

Idea

DFS

Code

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

Complexity

Time: O(N) Space: O(log N)

forestie9 commented 2 years ago

Idea

Use recursion, the max depth of left or right child plus 1 is the max depth of the tree

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

Complexity

O(n) time: traverse each node O(log(n)) space: if tree is balanced, the space is height of tree

maybetoffee commented 2 years ago

class Solution {
    int res = 0;
    int currDepth = 0;
    public int maxDepth(TreeNode root) {
        traverse(root);
        return res;
    }

    private void traverse(TreeNode root){
        if(root == null) return;

        currDepth++;
        res = Math.max(res, currDepth);
        traverse(root.left);
        traverse(root.right);
        currDepth--;
    }
}
class Solution2 {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;

        int depthLeft = maxDepth(root.left);
        int depthRight = maxDepth(root.right);
        return Math.max(depthLeft, depthRight)+1;       

    }
}

nancychien commented 2 years ago

思路: Recursion: Height = 1 + Max(height(left), height(right))

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

Time: O(n) Space: worst case - O(n) best case (more balanced) - O(log(n))

zhiyuanpeng commented 2 years ago

class Solution:

    def helper(self, root, d):
        if not root:
            return d
        d_l = self.helper(root.left, d+1)
        d_r = self.helper(root.right, d+1)
        return max(d_l, d_r)

    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return self.helper(root, 0)

time O(N) space O(logN)

dzwhh commented 2 years ago

【Day 13】104. Maximum Depth of Binary Tree 「二叉树的最大深度」

题目地址: https://leetcode-cn.com/problems/maximum-depth-of-binary-tree

题目描述

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。

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

3 / \ 9 20 / \ 15 7

前置知识

二叉树
递归

思路

从宏观的角度，先确定最基本问题，也就是终止条件是什么，然后把原问题转化成更小的问题，递归本身还是调用子函数的过程，只是这个子函数是自身，可想象成调用了一个功能相同的函数从微观的角度，每次调用子函数就是调用程序栈把子函数压入栈，直到满足终止条件后层层pop出去，把最小问题的结果返回上层函数

代码

js 版本

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

复杂度分析

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

MoonLee001 commented 2 years ago

思路

二叉树后序遍历

代码

var maxDepth = function(root) { 
    const dfs = (root) => {
        if (root == null) {
            return 0;
        }
        const left = maxDepth(root.left);
        const right = maxDepth(root.right);

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

    return dfs(root);
}

复杂度分析

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

currybeefer commented 2 years ago

思路：这题没啥好说的呀，就是遍历二叉树，找最大的深度呗，很简单代码：

 int maxDepth(TreeNode* root) 
    {
        return dp(root);
    }
    int dp(TreeNode* root)
    {
        if(root==nullptr)
            return 0;

        int a=dp(root->left);
        int b=dp(root->right);

        return max(a,b)+1;
    }
    int max(int a, int b)
    {
        return a>b? a:b;
    }

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

YuyingLiu2021 commented 2 years ago

#solution1 深度优先搜索(DFS)

#时间复杂度: O(N)
#空间复杂度: O(N) / O(height) 树的高度

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        ldepth = self.maxDepth(root.left)
        rdepth = self.maxDepth(root.right)
        if ldepth > rdepth: #或者直接一句：return max(rdepth, rdepth) +1
            return ldepth+1
        return rdepth +1 #要加上根节点的1

#solution2 ：宽度优先遍历(BFS) + Queue
#时间复杂度: O(N)
#空间复杂度: O(N) / O(weight) 树的宽度

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

        queue = [root]
        while queue:
            size = len(queue)
            for i in range(size):
                cur_node = queue.pop(0)
                if cur_node.left:
                    queue.append(cur_node.left)
                if cur_node.right:
                    queue.append(cur_node.right)
            height += 1
        return height

zqwwei commented 2 years ago

Code

    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root: return 0

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

BlueRui commented 2 years ago

Problem 104. Maximum Depth of Binary Tree

Algorithm

Recursively get the maxDepth of left and right sub tree. Final result is max(leftDepty, rightDepth) + 1.

Complexity

Time Complexity: O(N) where N is the total number of nodes.
Space Complexity: O(h) where h is the height of the tree.

Code

Language: Java

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

Davont commented 2 years ago

code

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

Ellie-Wu05 commented 2 years ago

思路：recursive

二叉树的深度是 root 子树高度+1 （root自己）所以可以用递归

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        else:
            left_max = self.maxDepth(root.left)
            right_max = self.maxDepth(root.right)

        return max(left_max,right_max)+1

复杂度分析

时间：我们只遍历一遍所以是On \ 空间：如果这个tree是相对平衡的二叉树，我们可以实现 Ologn，最差的情况是On

ShawYuan97 commented 2 years ago

代码

语言支持：Python3

Python3 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:
        """
        找出二叉树的最大深度

        Args:
            root(Optiona[TreeNode]):根节点

        Returns:
            depth(int):树的深度
        """
        """
        采用迭代的方法，如果知道左子树深度、左子树深度，那么当前树的深度就是max(左子树深度，右子树深度)+1
        """
        if not root:
            return 0
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)
        return max(left_depth,right_depth)+1

复杂度分析

令 n 为数组长度。

时间复杂度：$O(logn)$
空间复杂度：$O(logn)$

Magua-hub commented 2 years ago


class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        int res = 0;
        queue<TreeNode*> q;
        q.push(root);
        while(q.size()) {
            int n = q.size();
            while(n --) {
                auto t = q.front();
                q.pop();
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right); 
            }
            res ++;
        }
        return res;
    }
};

VictorHuang99 commented 2 years ago

Idea: 递归子树，找到最深.然后比较左右子树最深，提出最深+1

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

Complicity: 时间：O（n）空间：O（n）

EggEggLiu commented 2 years ago

var maxDepth = function(root) {
    if (!root) {
        return 0;
    }
    let res = 1;
    let dfs = function(node, depth) {
        if (node.left) {
            dfs(node.left, depth + 1);
        }
        if (node.right) {
            dfs(node.right, depth + 1);
        }
        res = Math.max(res, depth);
    }
    dfs(root, 1);
    return res;
};

okbug commented 2 years ago

思路

递归

代码

语言：JavaScript

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

freedom0123 commented 2 years ago

class Solution {
    public static int dfs(TreeNode node) {
        // 定义一个变量，记录答案，结果为求最大值，答案赋值为最小值
        int res = Integer.MIN_VALUE;
        // 如果说该节点为空，返回 0
        if(node == null) return 0;
        // 如果说左子树不为空，左子树上深度就是 1 + 左子树的深度
        if(node.left != null) res = Math.max(res,1+dfs(node.left));
        // 如果说右子树不为空，右子树上深度就是 1 + 右子树的深度
        if(node.right != null) res = Math.max(res,1+dfs(node.right));
        // 如果说初始值没有被改变过，说明只有该节点一个节点
        if(res == Integer.MIN_VALUE) return 1;
        // 返回结果
        return res;
    }
    public int maxDepth(TreeNode root) {
        return dfs(root);
    }
}

BiN214 commented 2 years ago

思路

二叉树深度为左右子树深度+1

代码

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

hyh331 commented 2 years ago

Day13 思路

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

某层的执行过程：在返回值部分基本已经描述清楚

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

复杂度分析

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

kite-fly6618 commented 2 years ago

思路：

后序遍历

代码：

//后序遍历
var maxDepth = (root) => {
    if(!root){
        return 0;
    }
    var leftDeep = maxDepth(root.left);// 左边深度
    var rightDeep = maxDepth(root.right);// 右边的深度
    return Math.max(leftDeep,rightDeep) + 1;// 取两者的最大值，在+1(当前节点)
}

复杂度：

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

KWDFW commented 2 years ago

Day13

104、二叉树的最大深度

javascript #树

1、遍历树

2、每层都加一，选左右两个子树中最大的返回

3、递归调用

代码

var maxDepth = function(root) {
    if(!root) return 0
    const l=maxDepth(root.left)
    const r=maxDepth(root.right)
    if(l>r) return l+1
    else return r+1
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

KelvinG-LGTM commented 2 years ago

思路 1 - 递归

递归

递归定义: maxDepth返回最大深度递归逻辑: 递归地取左右子树, 取最大深度. + 1

代码

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

复杂度分析

时间复杂度

O(N)

空间复杂度

O(树的高度既logN)

KelvinG-LGTM commented 2 years ago

思路 - BFS

在计算每一层时, 把当前depth + 1. 只需要调用bfs模板就行了.

代码

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        queue = deque()
        if not root: 
            return 0

        queue.append(root)
        depth = 0
        while queue: 
            q_len = len(queue)
            depth += 1
            for _ in range(q_len): 
                cur = queue.popleft()
                if cur.left: 
                    queue.append(cur.left)
                if cur.right: 
                    queue.append(cur.right)

        return depth

复杂度分析

时间复杂度

O(N)

空间复杂度

O(最后一层的节点数) height= logN. 最后一层的节点数 = 2 ^ height = N -> O(N)

flaming-cl commented 2 years ago

104. 二叉树的最大深度

复杂度

时间：O(N)
- n 二叉树节点个数
- 每个节点在递归中只被遍历一次
空间：O(height)
- height 二叉树高度
- 递归函数需要栈空间，而栈空间取决于递归的深度

代码

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

Orangejuz commented 2 years ago

题目

104. 二叉树的最大深度

思路

递归，终止条件：root为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: Optional[TreeNode]) -> int:
        if not root:
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return max(left,right)+1

复杂度

时间复杂度：O(N)

空间复杂度：O(1)

xingchen77 commented 2 years ago

思路

递归即可

代码

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

复杂度

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

houmk1212 commented 2 years ago

思路

树的最大深度，就是左子树和右子树中最大深度最大的那个+1。递归求解即可。

代码

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

复杂度

时间复杂度：O(N) N是树中的节点数量。
空间复杂度：O(Height) 是树的深度

caterpillar-0 commented 2 years ago

思路（深度优先搜索）

代码

class Solution {
public:
    int maxDepth(TreeNode* root) {
        //DFS深度优先搜索
        if(root==nullptr){
            return 0;
        }
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }
};

复杂度分析

时间复杂度：o(n)每个节点遍历一遍

空间复杂度：递归深度为树的深度，o(height)

思路（广度优先搜索）

代码

class Solution {
public:
int maxDepth(TreeNode* root) {
    //广度优先搜索，使用队列
    if(root==nullptr){
        return 0;
    }
    queue<TreeNode*> res;
    res.push(root);
    int ans=0;
    while(!res.empty()){
        int size=res.size();
        while(size){
            TreeNode* tmp=res.front();
            res.pop();
            if(tmp->left!=nullptr){
                res.push(tmp->left);
            }
            if(tmp->right!=nullptr){
                res.push(tmp->right);
            }
            --size;
        }
        ++ans;
    }
    return ans;
}
};

复杂度分析

时间复杂度：o(n)
空间复杂度：取决于队列中的元素

oneline-wsq commented 2 years ago

思路

递归，深度优先搜索

代码

# 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
        else:
            left_height=self.maxDepth(root.left)
            right_height=self.maxDepth(root.right)
            return max(left_height,right_height)+1

复杂度分析

时间复杂度：O(n)

空间复杂度：O(height)

Serena9 commented 2 years ago

代码

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

1973719588 commented 2 years ago

思路

广度优先遍历

代码

from collections import deque
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # BFS 广度遍历比较清晰
        if root == None:
            return 0

        steps = 0
        que = deque()
        que.appendleft(root)

        while que:
            l = len(que)
            for _ in range(l):
                node = que.pop()
                if node.right:
                    que.appendleft(node.right)
                if node.left:
                    que.appendleft(node.left)

            steps = steps + 1

        return steps

复杂度

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

ha0cheng commented 2 years ago

思路：递归遍历，假定F(node)可以计算以node为根节点的最大深度，那么有递推式F(node) = 1 + max(F(node.left),F(node.right)). 最后补充递归终止条件，if node==None:F(node) =0.

代码如下：

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

时间复杂度：O(N)，本质上相当于深度优先遍历，DFS 空间复杂度：O(maxDepth)，回归栈的深度最深为树的最大深度。

JasonHe-WQ commented 2 years ago

思路：层序遍历，用列表记录每棵子树，然后如果列表不为空，level += 1 代码：

# 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):
        if root is None: 
            return 0 
        q = [root]
        level = 1
        while q:
            child = []
            for i in q:
                if i.left:
                    child.append(i.left)
                if i.right:
                    child.append(i.right)
            if child:
                level += 1
            q = child
        return level

复杂度： O(n)

Jessie725 commented 2 years ago

Idea

Recursion: The max depth of binary tree is the deeper subtree of it plus 1

Code

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

Complexity

Time: O(n) n refers to the totla number of nodes of the tree Space: O(height) height of the tree

wychmod commented 2 years ago

思路

递归遍历左右子树，返回深度。取max

代码

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        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

复杂度分析

时间复杂度 On 空间复杂度 Odeep

Quieter2018 commented 2 years ago

思路递归操作，遍历左右子树，深度=左右子树深度的最大值+1（根节点）

代码

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

复杂度分析 时间复杂度：O(n), n 节点个数；空间复杂度：O(height), 递归开辟空间

LyuliangLiu commented 2 years ago

Idea

recursion
bfs
Code

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

class Solution {
public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    Queue<TreeNode> q = new LinkedList<>();
    int depth = 0;
    q.add(root);
    while (!q.isEmpty()) {
        depth++;
        int curLevel = q.size();
        for (int i = 0; i < curLevel; i++) {
            TreeNode cur = q.poll();
            if (cur.left != null) {
                q.add(cur.left);
            }
            if (cur.right != null) {
                q.add(cur.right);
            }
        }
    }
    return depth;
}
}

Complexity

Time: O(N). Space: best O(logn), worst O(N)

wenliangchen commented 2 years ago

思路

直接递归然后判断最大值即可

代码

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;

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

复杂度

Time: O(N)
Space: O(N)

CarrieyqZhang commented 2 years ago

recursion: keep searching left and right child, if null, retun null; else compare left and right return max + 1

code

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

time complexity: O(n) space complexity: O(height)

xixiao51 commented 2 years ago

思路

Recursion：DFS - 左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为max(l,r)+1
BFS: 用Queue存放当前层的所有节点，然后根据当前队列的size来寻找下一层的子节点直到队列为空，寻找的次数就是深度

代码

DFS:

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

BFS:

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        int height = 0;
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size > 0) {
                TreeNode node = queue.poll();
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
                size--;
            }
            height++;
        }

        return height;
    }
}

复杂度

DFS:

时间复杂度：O(n)，其中 n 为二叉树节点的个数。
空间复杂度：O(height)，其中height表示二叉树的高度。

BFS:

时间复杂度：O(n)，其中 n 为二叉树节点的个数。
空间复杂度：O(n)

pureryuDo commented 2 years ago

思路

树的最大深度为左右子树深度+1取max

代码

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

复杂度分析

time：O（N）

space：O(height)

sallyrubyjade commented 2 years ago

思路

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

代码

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

    let depthL = maxDepth(root.left);
    let depthR = maxDepth(root.right);

    return Math.max(depthL, depthR) + 1;
};

复杂度分析

时间复杂度：O(n)
空间复杂度：O(height)，即最好情况O(logn)，最坏情况O(n)

m908 commented 2 years ago

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

weihaoxie commented 2 years ago

思路

如果当前节点为空则返回0

返回当前节点的左子树和右子树层两者的最大深度+1

代码

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
def maxDepth(self, root):
    """
    :type root: TreeNode
    :rtype: int
    """
    if root is None:
        return 0
    else:
        return 1 + max(self.maxDepth(root.left),self.maxDepth(root.right))

复杂度

时间复杂度O(n)
空间复杂度O(深度)

leetcode-pp / 91alg-7-daily-check

【Day 13 】2022-04-13 - 104. 二叉树的最大深度 #15

104. 二叉树的最大深度

入选理由

题目地址

前置知识

题目描述

思路

代码

复杂度

思路

复杂度

代码

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

Idea

Code

Complexity

Idea

Complexity

【Day 13】104. Maximum Depth of Binary Tree 「二叉树的最大深度」

题目描述

前置知识

思路

代码

复杂度分析

思路

代码

复杂度分析

Code

Problem 104. Maximum Depth of Binary Tree

Algorithm

Complexity

Code

code

思路：recursive

复杂度分析

代码

思路

代码

思路

代码

Day13 思路

复杂度分析

思路：

代码：

复杂度：

javascript #树

代码

复杂度分析

思路 1 - 递归

递归

代码

复杂度分析

时间复杂度

空间复杂度

思路 - BFS

代码

复杂度分析

时间复杂度

空间复杂度

104. 二叉树的最大深度

复杂度

代码

题目

104. 二叉树的最大深度

思路

代码

复杂度

思路

代码

复杂度

思路

代码

复杂度

思路（深度优先搜索）

代码

复杂度分析

思路（广度优先搜索）

代码

复杂度分析