gpt4 book ai didi

104. Maximum Depth of Binary Tree 二叉树的最大深度

转载 作者:大佬之路 更新时间:2024-01-31 14:21:52 26 4
gpt4 key购买 nike

题目地址:https://leetcode.com/problems/maximum-depth-of-binary-tree/open in new window

Total Accepted: 85334 Total Submissions: 188240 Difficulty: Easy

题目描述

Given a binary tree, find its maximum depth.

Themaximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

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

    3
   / \
  9  20
    /  \
   15   7

return its depth = 3.

题目大意

求一颗二叉树的高度。

解题方法

方法一:BFS

求树的高度,可以从根节点开始,每次向下走一层,直到所有的节点遍历结束。层数就是高度。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        depth = 0
        que = collections.deque()
        que.append(root)
        while que:
            size = len(que)
            for _ in range(size):
                node = que.popleft()
                if not node:
                    continue
                que.append(node.left)
                que.append(node.right)
            depth += 1
        return depth - 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

方法二:DFS

运用递归,如果该节点是空,那么高度是0。否则树的高度等于 1 + 左子树和右子树高度的最大值。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com