二叉树深度

1、题目

image-20231020160911754

2、题解

方法1：递归

思路：如果结点存在则返回结点左右子树深度的最大值加1（\(root_{depth}=max(left_{depth},right_{depth})+1\)）,如果

左右子树为空则返回0。

代码实现：

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

方法2：层遍历

思路：遍历每层的结点，用队列对结点进行存储。每次存储下一层结点时，深度加1。

代码实现：

import queue
class Solution:
    def maxDepth(self , root: TreeNode) -> int:
        # 空节点没有深度
        if not root: 
            return 0
        # 队列维护层次后续节点
        q= queue.Queue() 
        # 根入队
        q.put(root) 
        # 记录深度
        res = 0
        # 层次遍历
        while not q.empty(): 
            # 记录当前层有多少节点
            n = q.qsize() 
            # 遍历完这一层，再进入下一层
            for i in range(n): 
                node = q.get()
                # 添加下一层的左右节点
                if node.left: 
                    q.put(node.left)
                if node.right:
                    q.put(node.right)
            # 深度加1
            res += 1 
        return res