首页 > 试题广场 >

二叉树的深度

[编程题]二叉树的深度

热度指数：383899 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度，根节点的深度视为 1 。

数据范围：节点的数量满足 $0 \le n \le 100$ ，节点上的值满足 $0 \le val \le 100$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

假如输入的用例为{1,2,3,4,5,#,6,#,#,7}，那么如下图:

示例1

输入

{1,2,3,4,5,#,6,#,#,7}

输出

示例2

输入

{}

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Python

JchengGit

一行代码搞定

class Solution:
    def TreeDepth(self, pRoot):
        return 0 if not pRoot else 1 + max(self.TreeDepth(pRoot.left), self.TreeDepth(pRoot.right))

发表于 2021-07-06 09:49:47 回复(0)

Python

牛客541273514号

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if not pRoot:
            return 0
        if not pRoot.left and not pRoot.right:
            return 1
        left=self.TreeDepth(pRoot.left)
        right=self.TreeDepth(pRoot.right)
        return max(left,right)+1

发表于 2021-05-02 00:56:12 回复(0)

Python

在下小6

python解法：
解法1:前序递归遍历；

class Solution:
    def TreeDepth(self, pRoot):
        if pRoot is None:
            return 0
        left = self.TreeDepth(pRoot.left)
        right = self.TreeDepth(pRoot.right)
        return max(left, right) + 1

解法2:非递归：层次遍历；

class Solution:
    def TreeDepth(self, pRoot):
        if pRoot is None:
            return 0
        depth = 0
        q = [] # 设置队列q存储节点；
        q.append(pRoot) # 根结点入队；
        while q:
            for i in range(len(q)): # 遍历同一层节点；
                p = q.pop(0) # 队头元素出队；
                if p.left is not None: # 左子树不空，左子树入队列；
                    q.append(p.left)
                if p.right is not None: # 右子树不空，右子树入队列；
                    q.append(p.right)
            depth += 1 # 深度+1
        return depth

发表于 2021-02-21 09:44:48 回复(0)

Python

牛客209879436号

from collections import deque
class Solution:
    def TreeDepth(self, pRoot):
        # write code her
        squeue = deque()
        squeue.append(pRoot)
        n = 0
        if pRoot is None:
            return n
        while len(squeue):
            tmp = []
            q = len(squeue)
            for i in range(q):
                node = squeue.popleft()
                if node.left is not None:
                    squeue.append(node.left)
                if node.right is not None:
                    squeue.append(node.right)
                tmp.append(node.val)
            if len(tmp) > 0:
                n+=1
        return n

利用二叉树的层次遍历，通过记录每层节点，来输出深度

发表于 2020-11-13 11:27:39 回复(0)

Python

老和山小学生

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if not pRoot:
            return 0
        LeftDepth = self.TreeDepth(pRoot.left)
        RightDepth = self.TreeDepth(pRoot.right)
        if LeftDepth > RightDepth:
            return LeftDepth + 1
        return RightDepth + 1

发表于 2020-10-16 12:06:59 回复(0)

Python

DDooo

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        if pRoot == None:
            return 0
        def recur(root,level):
            maxlevel = level
            if root.left!=None:
                maxlevel = max(maxlevel,recur(root.left,level+1))
            if root.right!=None:
                maxlevel = max(maxlevel,recur(root.right,level+1))
            return maxlevel
        return recur(pRoot,1)

注意：

1，在recur()函数中，左右节点是同时遍历的，进入递归之后，左右分支各自工作，深度大的分支会继续工作，所有maxlevel会不断增加。

2，开始我会疑惑，max()中的maxlevel不应该是maxlevel+1嘛，后来看到level+1知道，如果子节点不为空，那么肯定会再次进入recur()函数，所有此时的maxlevel=level+1了。

发表于 2020-07-22 15:28:10 回复(0)

Python

自律人偶

Python

1、利用栈来进行深度优先遍历。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.stack=[]#栈
        self.depth=0

    def DFS(self,root):
        if not root:return None
        self.stack.append(root)
        if not root.left and not root.right:#到达叶子结点
            if self.depth<len(self.stack):self.depth=len(self.stack)#如果深度大于记录值，则更新。
        else:
            self.DFS(root.left)
            self.DFS(root.right)
        del self.stack[-1]#将栈顶元素弹出，即回溯

    def TreeDepth(self, pRoot):
        # write code here
        self.DFS(pRoot)
        return self.depth

发表于 2020-06-11 23:34:28 回复(0)

Python

Kuriyamaaa

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        ll=[]

    def TreeDepth(self, pRoot):
        zhan=[]
        flag=[]
        p=pRoot
        if p==None:
            return 0
        if p.left==None and p.right==None:
            return 1

        return max(self.TreeDepth(p.left),self.TreeDepth(p.right))+1
            
            
        # write code here

发表于 2020-05-29 22:55:26 回复(0)

Python

努力学习的小贺

class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if pRoot==None:
            return 0
        queue=[(pRoot,1)]
        max_list=[]
        while len(queue)>0:
            subroot=queue.pop(0)
            t=subroot[0]
            count=subroot[1]
            max_list.append(count)
            if t.left:
                queue.append((t.left,count+1))
            if t.right:
                queue.append((t.right,count+1))
        return max_list[-1]

发表于 2020-04-01 13:10:00 回复(0)

Python

牛魔王，咦，我的压寨夫人呢

递归的方式：

class Solution:
def TreeDepth(self, pRoot):
# write code here
if not pRoot:
return 0
depth = 1
depth = self.recursion(pRoot, depth)
return depth

def recursion(self, p, d):
d1 = d
d2 = d
if p.left:
d1 = self.recursion(p.left, d+1)
if p.right:
d2 = self.recursion(p.right, d+1)
return max(d1, d2)

发表于 2020-03-06 10:03:50 回复(0)

Python

牛客447097232号

#-*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def TreeDepth(self, pRoot):
        """
        节点的深度 = 左右子节点的深度的最大 + 1
        :param pRoot:
        :return:
        """
        if not pRoot:
            return 0
        else:
            return 1 + max(self.TreeDepth(pRoot.left), self.TreeDepth(pRoot.right))


t = TreeNode(8)
t.left = TreeNode(6)
t.right = TreeNode(10)
t.left.left = TreeNode(5)
t.left.right = TreeNode(7)
t.right.left = TreeNode(9)
t.right.right = TreeNode(11)
s = Solution()
ans = s.TreeDepth(t)
print(ans)

发表于 2020-03-03 11:04:18 回复(0)

Python

朝夕_

class Solution:
    def TreeDepth(self, pRoot):
        # edge
        if not pRoot:
            return 0
        return 1 + max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right))

编辑于 2020-03-03 13:55:09 回复(0)

Python

aishuishui

class Solution:
def __init__(self):
self.depth = 0
self.maxdepth = 0
def TreeDepth(self, pRoot):
if pRoot == None:
return 0
self.depth += 1
if pRoot.left == None and pRoot.right == None:
if self.depth > self.maxdepth:
self.maxdepth = self.depth
self.TreeDepth(pRoot.left)
self.TreeDepth(pRoot.right)
self.depth -= 1
return self.maxdepth

发表于 2020-02-17 20:03:39 回复(0)

Python

海大_Man

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        high = 0
        if not pRoot:
            return 0
        stack = []
        stack.append((pRoot,[pRoot.val]))
        while stack:
            node,path = stack.pop(0)
            if node.left == None and node.right == None:
                tmp = len(path)
                if tmp > high:
                    high = tmp
            if node.left != None:
                stack.append((node.left,path + [node.left.val]))
            if node.right != None:
                stack.append((node.right,path + [node.right.val]))
        return high

编辑于 2020-01-05 21:15:01 回复(0)

Python

黄沙遮天

class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        #对于那些为空的节点
        if pRoot==None:
            return 0
        l1=0
        l2=0
        if pRoot!=None and pRoot.left==None and pRoot.right==None:
            #对于叶子节点，考虑这两个终止条件
            return 1
        if pRoot.left!=None:
            #左子树如果存在，就计算将根节点包含在内的左子树的高度
            l1=1+self.TreeDepth(pRoot.left)
        if pRoot.right!=None:
            #右子树如果存在，就计算将根节点包含在内的右子树的高度
            l2=1+self.TreeDepth(pRoot.right)
        #然后将左右子树的最大值赋值给根节点，通过递归的方式来得到树的最大深度
        length1=l1 if l1>l2 else l2
        return length1

本题通过递归的方法，分别计算出左子树和右子树的高度，然后将其中的最大值加1作为根节点的高度。需要注意的是递归结束的条件是为空和非空但是左右子树都不存在

发表于 2020-01-04 21:48:43 回复(1)

Python

天山剑客

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if pRoot == None:
                return 0
        else:
                return max(self.TreeDepth(pRoot.left), self.TreeDepth(pRoot.right)) + 1

发表于 2019-11-30 22:34:04 回复(0)

Python

卑微求offer的硕狗在读

层次遍历法

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        # 层次遍历法
        rootlist=[pRoot]
        depth=0
        while rootlist:
            temp=[]
            for i in rootlist:
                if i:    #要加入这一步，保证非None，因为None没有left与right
                    temp.append(i.left)
                    temp.append(i.right)
            rootlist=temp
            depth=depth+1

        return depth-1  #因为最终的rootlist是包括None节点的，所以需要把这一层的深度减去

发表于 2019-11-27 11:45:55 回复(0)

Python

秋水中的鱼

递归求解,当前节点的深度为其左节点和右节点深度的最大值再加一,递归终止条件是节点为空

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        if not pRoot:
            return 0
        return max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right))+1

发表于 2019-11-08 13:03:34 回复(0)

Python

我要扛offer回家

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if not pRoot:
            return 0
        else:
            left=self.TreeDepth(pRoot.left)
            right=self.TreeDepth(pRoot.right)
            return 1+max(left,right)

发表于 2019-10-06 16:46:09 回复(0)

提交观点

问题信息

树

来自：“一战通offer”互...

难度：

48条回答 1112收藏 107396浏览

通过挑战的用户

查看代码

GH9805

2023-03-08 11:34:16
Elastic...

2023-02-05 21:34:05
牛客44742...

2022-09-16 16:14:53
躺平了的大魔王很理智

2022-09-16 14:40:45
讲道理的小饼干...

2022-09-16 11:49:22

二叉树的深度

输入

输出

输入

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

Python

问题信息

热门推荐

通过挑战的用户

相关试题