剑指offer 二叉树的深度 python

xiaoxiao2021-08-29  1K+

题目描述

输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

样例

返回深度即可

想法一: 递归遍历

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

想法二: 使用队列,以元组保存节点和节点深度,如果存在左右节点,就将左右节点和当前节点深度加一入队,每次出队一个节点,知道队空。

class Solution: def TreeDepth(self, pRoot): # write code here return self.depth(pRoot) def depth(root): if root is None: return 0 dq = list() dq.append((root, 1)) while dq: node, layer = dq.pop(0) deep = layer if node.left: dq.append((node.left, layer + 1)) if node.right: dq.append((node.right, layer + 1)) return deep

最后

刷过的LeetCode或剑指offer源码放在Github上了,希望喜欢或者觉得有用的朋友点个star或者follow。 有任何问题可以在下面评论或者通过私信或联系方式找我。 联系方式 QQ:791034063 Wechat:liuyuhang791034063 :https://blog.csdn.net/Sun_White_Boy Github:https://github.com/liuyuhang791034063