用腾讯云做会员网站,哪里做网站的,免费网站建设行情,北京有哪些大型互联网公司二叉树最大深度
给定一个二叉树 root #xff0c;返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1#xff1a; 输入#xff1a;root [3,9,20,null,null,15,7] 输出#xff1a;3
递归法
本题可以使用前序#xff08;中左…二叉树最大深度
给定一个二叉树 root 返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1 输入root [3,9,20,null,null,15,7] 输出3
递归法
本题可以使用前序中左右也可以使用后序遍历左右中使用前序求的就是深度使用后序求的是高度。 二叉树节点的深度指从根节点到该节点的最长简单路径边的条数或者节点数取决于深度从0开始还是从1开始 二叉树节点的高度指从该节点到叶子节点的最长简单路径边的条数或者节点数取决于高度从0开始还是从1开始 而根节点的高度就是二叉树的最大深度所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。 这一点其实是很多同学没有想清楚的很多题解同样没有讲清楚。 体现后序遍历的过程使用前序的话要复杂的多 递归第一点参数就是传入树的根节点返回就返回这棵树的深度所以返回值为int类型。 递归第二点如果为空节点的话就返回0表示高度为0。 递归第三点 **先求它的左子树的深度再求右子树的深度最后取左右深度最大的数值 再1 **加1是因为算上当前中间节点就是目前节点为根节点的树的深度。也就是高度
class solution:def maxdepth(self, root: treenode) - int:return self.getdepth(root)def getdepth(self, node):if not node:return 0leftdepth self.getdepth(node.left) # 左rightdepth self.getdepth(node.right) # 右depth max(leftdepth, rightdepth) 1 # 中return depth精简版
class solution:def maxdepth(self, root: treenode) - int:if not root:return 0return 1 max(self.maxdepth(root.left), self.maxdepth(root.right))层次遍历
from collections import dequeclass TreeNode(object):def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightclass Solution(object):def maxDepth(self, root)::type root: TreeNode:rtype: intif not root:return 0result []queue deque([root])while queue:level_result []for _ in range(len(queue)):cur queue.popleft()level_result.append(cur.val)if cur.left:queue.append(cur.left)if cur.right:queue.append(cur.right)result.append(level_result)return len(result) # 里面多少嵌套列表 即为最大深度参考 https://www.programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html
