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 。

LAGRANGIST commented 2 years ago

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

yetfan commented 2 years ago

思路递归

代码

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

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

yan0327 commented 2 years ago

思路： DFS深度搜索+后续遍历

func maxDepth(root *TreeNode) int {
    if root == nil{
        return 0
    }
    left := maxDepth(root.Left)
    Right := maxDepth(root.Right)
    if left > Right{
        return left+1
    }else{
        return Right+1
    }
}

时间复杂度O（n）遍历了所有树的节点空间复杂度O（h）树的深度

Alfie100 commented 2 years ago

LeetCode题目连接： 104. 二叉树的最大深度 https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

思路

DFS：深度优先搜索 BFS：广度优先搜索【层序遍历】

Python 代码

(1) DFS：

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

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

        return dfs(root)

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(h)，其中 h 为二叉树的高度。

(2) BFS：

# 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
        deque = collections.deque([root])
        depth = 0
        while deque:
            for _ in range(len(deque)):
                node = deque.popleft()
                if node.left:
                    deque.append(node.left)
                if node.right:
                    deque.append(node.right)
            depth += 1

        return depth

复杂度分析

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

BpointA commented 2 years ago

思路

递归

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;}
        if(root.left==null && root.right==null)
        {return 1;}
        int a=maxDepth(root.left);
        int b=maxDepth(root.right);
        if(a>b)
        {return 1+a;}
        return 1+b;

    }
}

SeventeenCui commented 2 years ago

思路

递归实现，相当于用了后序遍历的模板。

代码

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

复杂度分析

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

zwmanman commented 2 years ago

思路

Recursion

代码

# 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
        """
        return self.dfs(root)

    def dfs(self, root):
        if not root:
            return 0

        l = self.dfs(root.left)
        r = self.dfs(root.right)

        return max(l, r) + 1

复杂度分析

时间复杂度：O(logn)，其中 N Node. number。
空间复杂度：O(1)

RMadridXDH commented 2 years ago

代码

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

wxj783428795 commented 2 years ago

思路

如果当前节点为空，则以当前节点为子树的深度为0。
递归比较节点左右两侧子节的高度即可算出树的最大深度

代码

/**
 * @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) ，每个节点都会运行一次maxDepth
空间复杂度：O(depth)，函数调用栈占用的空间

zjsuper commented 2 years ago

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

Liuxy94 commented 2 years ago

思路

Ordered dict

代码

from collections import OrderedDict
class LRUCache(OrderedDict):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self:
            return - 1

        self.move_to_end(key)
        return self[key]

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.capacity:
            self.popitem(last = False)

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

复杂度分析

时间：O(1)

空间：O(dict)

ZhangNN2018 commented 2 years ago

思路

递归

复杂度

时间复杂度: O(N) ；
空间复杂度: O(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

feifan-bai commented 2 years ago

思路

Recursion, return the maxDepth of the left and right subtree

代码

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)
空间复杂度：O(Depth)

Bochengwan commented 2 years ago

思路

通过stack，层序遍历tree，每层增加层高计数。

代码

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        stack = [root]
        ans=0
        while stack:
            n = len(stack)
            for _ in range(n):
                curr = stack.pop(0)
                if curr.left:
                    stack.append(curr.left)
                if curr.right:
                    stack.append(curr.right)
            ans+=1
        return ans

复杂度分析

时间复杂度：O(N)，其中 N 为数组长度。
空间复杂度：O(logN)

Husky-Gong commented 2 years ago

Solution

Use recursion to get level value from root's left and right accordingly
compare left and right value, choose the maximum vale as depth

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 Complexity : O(N) Space Complexity : O(logN)

wangzehan123 commented 2 years ago

Java Code:


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

rzhao010 commented 2 years ago

Thoughts

Basic DFS

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

Complexity Time: O(n), each node will be visited once Space: O(height), the space for stack

AlduinLeung commented 2 years ago

DFS

/**
 * 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
    }else{
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right))  // 注意子问题这里要+1
    }
};

ref: https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/er-cha-shu-de-zui-da-shen-du-yi-dong-shi-6kil/

时间复杂度：O(n)

Liuxy94 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 not root: return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

复杂度分析

时间复杂度：O(n)

空间复杂度：O(logn)

zhangzz2015 commented 2 years ago

思路

方法1 使用前序遍历，传入parent节点的level，进入下一层。通过dfs找到最大深度。时间复杂度为O(n)，空间复杂度最差为O(n)，为树的深度
方法2 使用后序遍历，计算左右孩子节点深度，比较后得到root的深度，传回。时间复杂度为O(n)，空间复杂度最差为O(n)，为树的深度

关键点

代码

语言支持：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) {

        int ret =0; 
        dfs(root, 0, ret); 
        return ret; 
    }

    void dfs(TreeNode* root, int level, int& ret)
    {
        if(root == NULL)
            return; 

        ret = max(ret, level+1); 

        dfs(root->left, level+1, ret); 
        dfs(root->right, level+1, ret); 
    }
};

class Solution {
public:
    int maxDepth(TreeNode* root) {

        return dfs(root); 
    }

    int dfs(TreeNode* root)
    {
        if(root == NULL)
            return 0; 

        int ileft = dfs(root->left); 
        int iright = dfs(root->right); 
        return max(ileft, iright) +1; 
    }
};

CoreJa commented 2 years ago

思路

队列：非递归写法，用队列作为辅助栈模拟层序遍历的过程

递归：一行搞定，每次返回当前节点的深度，+1比较大小

代码


class Solution:
# 队列：非递归写法，用队列作为辅助栈模拟层序遍历的过程
def maxDepth1(self, root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    cnt = 0
    q = deque([root])
    while n := len(q):
        for i in range(n):
            node = q.popleft()
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        cnt += 1
    return cnt

# 递归：一行搞定，每次返回当前节点的深度，+1比较大小
def maxDepth(self, root: Optional[TreeNode]) -> int:
    return max(self.maxDepth(root.left) + 1, self.maxDepth(root.right) + 1) if root else 0

xj-yan commented 2 years ago

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

Time Complexity: O(n), Space Complexity: O(n)

laofuWF commented 2 years ago

# 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

freesan44 commented 2 years ago

思路

DFS实现

关键点

代码

语言支持：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: TreeNode) -> int:
        maxDepth = self.dfs(root, 0, 0)
        return maxDepth
    def dfs(self, node:TreeNode, cur:int, maxDepth:int) -> int:
        if node == None:
            # print(cur, maxDepth)
            return maxDepth
        cur += 1
        maxDepth = max(cur, maxDepth)
        leftMax = 0
        rightMax = 0
        if node.left:
            leftMax = self.dfs(node.left, cur, maxDepth)
        if node.right:
            rightMax = self.dfs(node.right, cur, maxDepth)
        # print(node.val,maxDepth,leftMax, rightMax)
        return max(leftMax, rightMax, maxDepth)

复杂度分析

令 n 为数组长度。

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

ZacheryCao commented 2 years ago

Idea

DFS. In the dfs function, the termination condition is the node is null, which returns 0. If current node is not null, we get its left subtree's depth and right subtree's depth. Then return 1 + max(left, right), because we need to find the max depth of current subtree whose root is current node. It means, we need to find the larger depth of current node's left subtree and right subtree and plus that value with current node's depth 1.

Cod

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 1 + max(left, right)

Complexity: Time: O(N). N: # of nodes Space: O(N). Recursion has O(N) space in the stack

Alexno1no2 commented 2 years ago

#递归求解，递归条件是节点为空（返回高度0）
#首先如果节点为空，返回高度为0；节点不空则继续递归
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        # if root.left is None and root.right is None:
        #     return 1
        return 1 + max(self.maxDepth(root.left),self.maxDepth(root.right))

Yrtryannn commented 2 years ago

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

falconruo commented 2 years ago

思路: 层序遍历

复杂度分析:

时间复杂度: O(n), n为树的节点数
空间复杂度: O(k)

代码(C++):

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;

        queue<TreeNode*> qt;
        qt.push(root);

        int depth = 0;
        while (!qt.empty()) {
            size_t size = qt.size();
            while (size--) {
                TreeNode* node = qt.front();
                qt.pop();
                if (node->left) qt.push(node->left);
                if (node->right) qt.push(node->right);
            }
            ++depth;
        }

        return depth;
    }
};

tongxw commented 2 years ago

思路

后序DFS

代码

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

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

SC: O(N) TC: O(logN)

nonevsnull commented 2 years ago

思路

//s6

思路与解法
Tree主要看遍历，DFS主要看写法；BFS主要看模版；
这里主要是定义好递归返回值；

代码

//s6
class Solution {
    public int maxDepth(TreeNode root) {
        return preOrder(root);
    }

    public int preOrder(TreeNode root) {
        if(root == null) return 0;

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

复杂度

dfs time: 虽然递归只进行了logN次，但是每个node依旧被遍历到了，因此时间复杂度还是O(N) space: 维护递归stack的空间，由递归的层数决定，因此为O(logN);

simbafl commented 2 years ago

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

Yark-yao commented 2 years ago

思路

简单题，树的题目都考虑使用递归，尤其是深度优先遍历，树的最大深度 = 1 + Math.max(左子树最大深度，右子树最大深度)

代码

/**
 * 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 {
    // 深度优先遍历 DFS
    if(root === null){
        return 0
    }
    const leftDepth = maxDepth(root.left)
    const rightDepth = maxDepth(root.right)
    return Math.max(leftDepth,rightDepth) + 1
};

复杂度：

时间：O（N）每个节点都会遍历一次空间：O（height） height是树的高度，递归需要栈空间

suukii commented 2 years ago

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

hdyhdy commented 2 years ago

思路：首先判断是否为空，如果是空就返回0.然后用递归的方式，寻找左右子树的深度最大值，这其中的最大值再加上1就是包含某个节点的最大深度。然后可以通过从根节点这样遍历得到答案。

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

func max(x,y int) int {
    if x > y {
        return x
    }else {
        return y
    }
}

复杂度：时间为n 空间为depth

Flower-F commented 2 years ago

解题思路

如果知道了左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为 maxDepth = max(l, r) + 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;
    }

    const left = maxDepth(root.left), right = maxDepth(root.right);
    const maxHeight = Math.max(left, right) + 1;

    return maxHeight;
};

复杂度

时间：O(N) N 为节点数空间：O(H) H 为树高度

de0002ou commented 2 years ago

思路

递归

代码


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)O(n)，其中 nn 为二叉树节点的个数。每个节点在递归中只被遍历一次。
空间复杂度：O(\textit{height})O(height)，其中 \textit{height}height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。

haixiaolu commented 2 years ago

思路

递归

代码 / Python

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)
空间复杂度：O(h)

SenDSproject commented 2 years ago

解题思路：可以用BFS 模版每层+1 或者DFS 递归，这里贴一个BFS的答案


class Solution(object):
    def maxDepth(self, root):
        if not root:
            return 0
        queue = collections.deque([root])
        depth = 0
        while queue:
            size = len(queue)
            depth +=1
            for _ in range(size):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return depth

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

iambigchen commented 2 years ago

思路

递归计算左右枝的最大高度+1，就是当前节点的高度。

关键点

代码

语言支持：JavaScript

JavaScript Code:


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

};

复杂度分析

令 n 为数组长度。

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

Toms-BigData commented 2 years ago

【Day 13】104. 二叉树的最大深度

思路

没啥说的，递归

golang代码

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return getDepth(root)
}
func getDepth(node *TreeNode) int {
    if node.Left == nil && node.Right == nil {
        return 1
    }
    var leftDepth, rightDepth int
    if node.Left != nil {
        leftDepth = getDepth(node.Left)
    }
    if node.Right != nil{
        rightDepth = getDepth(node.Right)
    }
    if leftDepth > rightDepth {
        return leftDepth+1
    }else {
        return rightDepth+1
    }
}

复杂度

时间:O(N) 空间:O(logN)

linyang4 commented 2 years ago

思路

递归获取左子树和右子树的深度, 然后比较大小

代码

var maxDepth = function(root) {
    if (!root) { return 0 }
    let leftDepth = maxDepth(root.left)
    let rightDepth = maxDepth(root.right)
    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1
};

复杂度

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

shamworld commented 2 years ago

思路

递归计算

代码

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

nweass commented 2 years ago

思路

BFS

层次遍历，每下一层，深度加1

DFS

深度遍历，递归返回左右子树的最大深度加1

代码


//BFS
public int maxDepth(TreeNode root) {
        int max = 0;
        if(root == null) return max;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);

        while(!queue.isEmpty()){
            int size = queue.size();
            while(size > 0){
                TreeNode cur = queue.poll();
                if(cur.left != null) queue.add(cur.left);
                if(cur.right != null) queue.add(cur.right);
                size--;
            }
            max++;
        }
        return max;
    }

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

    }

复杂度分析

BFS

while循环次数为二叉树的节点数，时间复杂度为O(n)

使用额外队列保存，空间复杂度为O(n)

DFS

时间复杂度：O(N)，其中 N 为节点数。

空间复杂度：O(h)，其中 h 为树的深度

devosend 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

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

        deep = left if left > right else right
        return deep + 1

复杂度分析

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

stackvoid commented 2 years ago

思路

深度递归遍历，返回每一个树节点 max(左节点深度，右节点深度)；直到叶子节点为止。
宽度遍历，多少层就是多少深度。

代码

语言支持：Java

Java Code:


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

复杂度分析

令 n 为数组长度。

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

Grendelta commented 2 years ago

思路

进行深度递归

代码

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

复杂度

时间复杂度 O(N)

空间复杂度 O(N)

ghost commented 2 years ago

思路

递归：求二叉树的最大深度，相当于求二叉树根节点的高度。

层序遍历：每遍历一层的同时，将深度+1。

代码

//递归
class Solution {
    public int maxDepth(TreeNode root) {
        return getHeight(root);
    }

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

//层序遍历
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            depth++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }
        return depth;
    }
}

复杂度分析

递归

时间复杂度：O(N)，其中 N 为二叉树的节点数。
空间复杂度：O(H)，其中 H 位二叉树的高度。

层序遍历

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

zhy3213 commented 2 years ago

思路

先序遍历非递归

代码

    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        q=deque([(root,0)])
        m=0
        while q:
            cur,depth=q.pop()
            while cur:
                depth+=1
                m=depth if m<depth else m
                if cur.right:
                    q.append((cur.right,depth))
                cur=cur.left
        return m

biaohuazhou commented 2 years ago

思路

递归

代码

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        //使用递归，因为根节点返回的是个int  直接递归左子树 右子树
        int leftDepth =maxDepth(root.left);
        int rightDepth=maxDepth(root.right);
        //因为当一个节点为叶节点时 其返回为0  因此需要加1
        return Math.max(leftDepth,rightDepth)+1;
    }
}

复杂度分析 时间复杂度： O(n) n为节点数每个节点都需要运行空间复杂度：O(h)h为树的深度

ZJP1483469269 commented 2 years ago

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

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

【Day 13 】2021-12-24 - 104. 二叉树的最大深度 #20

104. 二叉树的最大深度

入选理由

题目地址

前置知识

题目描述

思路

Python 代码

思路

Java代码

思路

代码

复杂度分析

思路

代码

代码

思路

代码

复杂度分析

思路

代码

复杂度分析

思路

复杂度

代码

思路

代码

Solution

Code

Complexity

DFS

思路

代码

复杂度分析

思路

关键点

代码

思路

代码

思路

关键点

代码

Idea

Cod

思路

代码

思路

代码

复杂度

思路

代码

复杂度：

S1: DFS

S2: BFS

解题思路

代码

复杂度

思路

代码

思路

代码 / Python

复杂度分析

思路

关键点

代码

【Day 13】104. 二叉树的最大深度

思路

golang代码

复杂度

思路

代码

复杂度

思路

代码

复杂度分析

思路

BFS

DFS

代码