垂直网站建设方案,网站规划与建设规划书,开发网站要多少钱,百度指数网页版二叉树的深度优先遍历题目是让我有点晕#xff0c;先把简单的层序遍历总结下吧#xff1a;配合队列进行的层序遍历在逻辑思维上自然直观#xff0c;不容易出错 102. 二叉树的层序遍历 本题是二叉树的层序遍历模板#xff1a;每次循环将一层节点出队#xff0c;再将一层节点… 二叉树的深度优先遍历题目是让我有点晕先把简单的层序遍历总结下吧配合队列进行的层序遍历在逻辑思维上自然直观不容易出错 102. 二叉树的层序遍历 本题是二叉树的层序遍历模板每次循环将一层节点出队再将一层节点入队也是所有可用层序遍历解二叉树题目的模板只需要在模板里稍加改动即可解题 from typing import List, Optional, Union
from collections import deque102. 二叉树的层序遍历
给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。
示例 1:输入root [3,9,20,null,null,15,7]输出[[3],[9,20],[15,7]]
题眼基础
思路利用队列实现
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightdef buildBinaryTree(nums: List[Union[int, str]]) - Optional[TreeNode]:if len(nums) 0:return Noneif len(nums) 1:return TreeNode(nums[0])# 1、转换为顺序存储tmpTree []for n in nums:if n ! null:tmpTree.append(TreeNode(n))else:tmpTree.append(None)# 2、转换为链式存储双指针root tmpTree[0]parent, child 0, 1while child len(tmpTree):if tmpTree[parent] ! None: # 双亲节点有效if tmpTree[child] ! None: # 左孩子节点有效tmpTree[parent].left tmpTree[child]child 1 # 指向右孩子if child len(tmpTree) and tmpTree[child] ! None: # 右孩子节点存在且有效tmpTree[parent].right tmpTree[child]child 1 # 指向下个节点的左孩子parent 1 # 更新遍历双亲节点return rootclass Solution:def levelOrder(self, root: Optional[TreeNode]) - List[List[int]]:if root None:return []result []que deque()que.append(root) # 队列初始值while len(que) 0:size len(que) # 当前队列长度二叉树一层的节点个数layer []for _ in range(size): # 一层遍历node que.popleft() # 记录下出队的节点layer.append(node.val)# 和之前深度遍历一样空节点不入队不然对None节点取值会出错if node.left ! None:que.append(node.left)if node.right ! None:que.append(node.right)result.append(layer)return resultif __name__ __main__:obj Solution()while True:try:in_line input().strip().split()[1].strip()[1: -1]nums []if in_line ! :for n in in_line.split(,):if n ! null:nums.append(int(n))else:nums.append(n)root buildBinaryTree(nums)print(obj.levelOrder(root))except EOFError:break107. 二叉树的层序遍历 II “102. 二叉树的层序遍历”的结果反转/逆序即可 from typing import List, Optional, Union
from collections import deque107. 二叉树的层序遍历 II
给你二叉树的根节点 root 返回其节点值 自底向上的层序遍历 。 即按从叶子节点所在层到根节点所在的层逐层从左向右遍历
示例 1:输入root [3,9,20,null,null,15,7]输出[[15,7],[9,20],[3]]
题眼自底向上的层序遍历
思路“102. 二叉树的层序遍历”的结果反转/逆序即可
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightdef buildBinaryTree(nums: List[Union[int, str]]) - Optional[TreeNode]:if len(nums) 0:return Noneif len(nums) 1:return TreeNode(nums[0])# 1、顺序存储tmpTree []for n in nums:if n ! null:tmpTree.append(TreeNode(n))else:tmpTree.append(None)# 2、链式存储双指针root tmpTree[0]parent, child 0, 1while child len(tmpTree):if tmpTree[parent] ! None: # 双亲节点有效if tmpTree[child] ! None: # 左孩子有效tmpTree[parent].left tmpTree[child]child 1 # 指向右孩子if child len(tmpTree) and tmpTree[child] ! None: # 右孩子存在且有效tmpTree[parent].right tmpTree[child]child 1 # 指向下个节点的左孩子parent 1return rootclass Solution:def levelOrderBottom(self, root: Optional[TreeNode]) - List[List[int]]:# 情况1、树为空if root None:return []# 情况2、树不为空que deque()que.append(root)result []while len(que) 0:size len(que) # 当前队列长度二叉树一层的节点个数layer []for _ in range(size): # 一层遍历node que.popleft()layer.append(node.val)if node.left ! None:que.append(node.left)if node.right ! None:que.append(node.right)result.append(layer)# 反转result# left, right 0, len(result) - 1# while left right:# result[left], result[right] result[right], result[left]# left 1# right - 1return result[::-1]if __name__ __main__:obj Solution()while True:try:in_line input().strip().split()[1].strip()[1: -1]nums []if in_line ! :for n in in_line.split(,):if n ! null:nums.append(int(n))else:nums.append(n)print(nums)root buildBinaryTree(nums)print(obj.levelOrderBottom(root))except EOFError:break429. N 叉树的层序遍历 一般 层序遍历的基础上要访问每个节点的N个孩子 from typing import List, Optional, Union
from collections import deque429. N 叉树的层序遍历
给定一个 N 叉树返回其节点值的层序遍历。即从左到右逐层遍历。
树的序列化输入是用层序遍历每组子节点都由 null 值分隔参见示例。
示例 1:输入root [1,null,3,2,4,null,5,6]输出[[1],[3,2,4],[5,6]]
题眼N 叉树的层序遍历
思路一般 层序遍历的基础上要访问每个节点的N个孩子
class Node:def __init__(self, valNone, childrenNone):self.val valself.children childrenclass Solution:def levelOrder(self, root: Node) - List[List[int]]:# 情况1、树为空if root None:return []# 情况2、树不为空que deque()que.append(root)result []while len(que) 0:size len(que)layer []for _ in range(size): # 一层遍历node que.popleft()layer.append(node.val)if node.children ! None:for child in node.children:que.append(child)result.append(layer)return result637. 二叉树的层平均值
from typing import List, Optional, Union
from collections import deque637. 二叉树的层平均值
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
示例 1:输入root [3,9,20,null,null,15,7]输出[3.00000,14.50000,11.00000]解释第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。因此返回 [3, 14.5, 11] 。
题眼每一层节点的平均值
思路一般 层序遍历的基础上计算每一层对应的平均值
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightdef buildBinaryTree(nums: List[Union[int, str]]) - Optional[TreeNode]:if len(nums) 0:return Noneif len(nums) 1:return TreeNode(nums[0])# 1、顺序存储tmpTree []for n in nums:if n ! null:tmpTree.append(TreeNode(n))else:tmpTree.append(None)# 2、转换为链式存储root tmpTree[0]parent, child 0, 1while child len(tmpTree):if tmpTree[parent] ! None: # 双亲节点有效if tmpTree[child] ! None: # 左孩子节点有效tmpTree[parent].left tmpTree[child]child 1 # 指向右孩子if child len(tmpTree) and tmpTree[child] ! None: # 右孩子存在且有效tmpTree[parent].right tmpTree[child]child 1 # 指向下个节点的左孩子parent 1return rootclass Solution:def averageOfLevels(self, root: Optional[TreeNode]) - List[float]:que deque()que.append(root)result []while len(que) 0:size len(que) # 当前队列长度二叉树一层的节点个数s 0for _ in range(size): # 一层遍历node que.popleft()s node.valif node.left ! None:que.append(node.left)if node.right ! None:que.append(node.right)result.append(s / size)return resultif __name__ __main__:obj Solution()while True:try:in_line input().strip().split()[1].strip()[1: -1]nums []if in_line ! :for n in in_line.split(,):if n ! null:nums.append(int(n))else:nums.append(n)root buildBinaryTree(nums)print(obj.averageOfLevels(root))except EOFError:break515. 在每个树行中找最大值
from typing import List, Optional, Union
from collections import deque515. 在每个树行中找最大值
给定一棵二叉树的根节点 root 请找出该二叉树中每一层的最大值。
示例 1:输入: root [1,3,2,5,3,null,9]输出: [1,3,9]
题眼二叉树的层序遍历
思路一般 层序遍历的基础上记录每一行的最大值
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightdef buildBinaryTree(nums: List[Union[int, str]]) - Optional[TreeNode]:if len(nums) 0:return Noneif len(nums) 1:return TreeNode(nums[0])# 1、转换为顺序存储tmpTree []for n in nums:if n ! null:tmpTree.append(TreeNode(n))else:tmpTree.append(None)root tmpTree[0]# 2、转换为链式存储双指针parent, child 0, 1while child len(tmpTree):if tmpTree[parent] ! None: # 双亲节点有效if tmpTree[child] ! None: # 左孩子有效tmpTree[parent].left tmpTree[child]child 1 # 指向右孩子if child len(tmpTree) and tmpTree[child] ! None: # 右孩子存在且有效tmpTree[parent].right tmpTree[child]child 1 # 指向下个节点的左孩子parent 1return rootclass Solution:def largestValues(self, root: Optional[TreeNode]) - List[int]:# 情况1、树为空if root None:return []# 情况2、树不为空que deque()que.append(root)result []while len(que) 0:size len(que) # 当前队列长度二叉树一层的节点个数n -float(inf)for _ in range(size): # 一层遍历node que.popleft()n max(n, node.val)if node.left ! None:que.append(node.left)if node.right ! None:que.append(node.right)result.append(n)return resultif __name__ __main__:obj Solution()while True:try:in_line input().strip().split()[1].strip()[1: -1]nums []if in_line ! :for n in in_line.split(,):if n ! null:nums.append(int(n))else:nums.append(n)root buildBinaryTree(nums)print(obj.largestValues(root))except EOFError:break199. 二叉树的右视图 一般 层序遍历的基础上返回每一层的最后一个元素 from typing import List, Optional, Union
from collections import deque199. 二叉树的右视图
给定一个二叉树的 根节点 root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。
示例 1:输入[1,2,3,null,5,null,4]输出[1,3,4]
题眼从顶部到底部 从右侧所能看到
思路一般 层序遍历的基础上返回每一层的最后一个元素
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightdef buildBinaryTree(nums: List[Union[int, str]]) - Optional[TreeNode]:if len(nums) 0:return Noneif len(nums) 1:return TreeNode(nums[0])# 1、 顺序存储tmpTree []for n in nums:if n ! null:tmpTree.append(TreeNode(n))else:tmpTree.append(None)# 2、链式存储双指针root tmpTree[0]parent, child 0, 1while child len(tmpTree):if tmpTree[parent] ! None: # 双亲结点有效if tmpTree[child] ! None: # 左孩子节点有效tmpTree[parent].left tmpTree[child]child 1 # 指向右孩子if child len(tmpTree) and tmpTree[child] ! None: # 右孩子节点存在且有效tmpTree[parent].right tmpTree[child]child 1 # 指向下个节点的左孩子parent 1return rootclass Solution:def rightSideView(self, root: Optional[TreeNode]) - List[int]:# 情况1、树为空if root None:return []# 情况2、树不为空que deque()que.append(root)result []while len(que) 0:size len(que)for i in range(size): # 一层遍历node que.popleft()if i size - 1: # 添加每一层的最后一个元素result.append(node.val)if node.left ! None:que.append(node.left)if node.right ! None:que.append(node.right)return resultif __name__ __main__:obj Solution()while True:try:in_line input().strip()[1: -1]nums []if in_line ! :for n in in_line.split(,):if n ! null:nums.append(int(n))else:nums.append(n)root buildBinaryTree(nums)print(obj.rightSideView(root))except EOFError:break513. 找树左下角的值 一般 层序遍历的基础上访问每一层的每个元素时都把第一个元素进行赋值即可 from typing import List, Optional, Union
from collections import deque513. 找树左下角的值
给定一个二叉树的 根节点 root请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:输入: root [2,1,3]输出: 1
题眼二叉树的层序遍历
思路一般 层序遍历的基础上访问每一层的每个元素时都把第一个元素进行赋值即可
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightdef buildBinaryTree(nums: List[Union[int, str]]) - Optional[TreeNode]:if len(nums) 0:return Noneif len(nums) 1:return TreeNode(nums[0])# 1、顺序存储tmpTree []for n in nums:if n ! null:tmpTree.append(TreeNode(n))else:tmpTree.append(None)root tmpTree[0]# 2、链式存储parent, child 0, 1while child len(tmpTree):if tmpTree[parent] ! None: # 双亲结点有效if tmpTree[child] ! None: # 左孩子节点有效tmpTree[parent].left tmpTree[child]child 1 # 指向右孩子if child len(tmpTree) and tmpTree[child] ! None: # 右孩子存在且有效tmpTree[parent].right tmpTree[child]child 1 # 指向下一个节点的左孩子parent 1return rootclass Solution:def findBottomLeftValue(self, root: Optional[TreeNode]) - int:que deque()que.append(root)result 0while len(que) 0:size len(que)for i in range(size):node que.popleft()if i 0: # 总是获取层序遍历的每一层第一个值result node.valif node.left ! None:que.append(node.left)if node.right ! None:que.append(node.right)return resultif __name__ __main__:obj Solution()while True:try:in_line input().strip().split()[1].strip()[1: -1]nums []if in_line ! :for n in in_line.split(,):if n ! null:nums.append(int(n))else:nums.append(n)root buildBinaryTree(nums)print(obj.findBottomLeftValue(root))except EOFError:break103. 二叉树的锯齿形层序遍历 一般 层序遍历的基础上对结果的偶数个逆序一下 from typing import List, Optional, Union
from collections import deque103. 二叉树的锯齿形层序遍历
给你二叉树的根节点 root 返回其节点值的 锯齿形层序遍历 。即先从左往右再从右往左进行下一层遍历以此类推层与层之间交替进行。
示例 1:输入root [3,9,20,null,null,15,7]输出[[3],[20,9],[15,7]]
题眼基础
思路一般 层序遍历的基础上对结果的偶数个逆序一下
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightdef buildBinaryTree(nums: List[Union[int, str]]) - Optional[TreeNode]:if len(nums) 0:return Noneif len(nums) 1:return TreeNode(nums[0])# 1、转换为顺序存储tmpTree []for n in nums:if n ! null:tmpTree.append(TreeNode(n))else:tmpTree.append(None)# 2、转换为链式存储双指针root tmpTree[0]parent, child 0, 1while child len(tmpTree):if tmpTree[parent] ! None: # 双亲节点有效if tmpTree[child] ! None: # 左孩子节点有效tmpTree[parent].left tmpTree[child]child 1 # 指向右孩子if child len(tmpTree) and tmpTree[child] ! None: # 右孩子节点存在且有效tmpTree[parent].right tmpTree[child]child 1 # 指向下个节点的左孩子parent 1 # 更新遍历双亲节点return rootclass Solution:def zigzagLevelOrder(self, root: Optional[TreeNode]) - List[List[int]]:# 情况1、树为空if root None:return []# 情况2、树不为空que deque()que.append(root)result []while len(que) 0:size len(que)layer []for _ in range(size):node que.popleft()layer.append(node.val)if node.left ! None:que.append(node.left)if node.right ! None:que.append(node.right)result.append(layer)# 对结果的偶数个逆序一下for i in range(1, len(result), 2):result[i] result[i][::-1]return resultif __name__ __main__:obj Solution()while True:try:in_line input().strip().split()[1].strip()[1: -1]nums []if in_line ! :for n in in_line.split(,):if n ! null:nums.append(int(n))else:nums.append(n)root buildBinaryTree(nums)print(obj.zigzagLevelOrder(root))except EOFError:break116. 填充每个节点的下一个右侧节点指针 一般 层序遍历的基础上将每层的节点除最后一个外的next值指向下一个节点 from typing import List, Optional, Union
from collections import deque116. 填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 其所有叶子节点都在同一层每个父节点都有两个子节点。二叉树定义如下
struct Node {int val;Node *left;Node *right;Node *next;
}
填充它的每个 next 指针让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点则将 next 指针设置为 NULL。
初始状态下所有next 指针都被设置为 NULL。
示例 1:输入root [1,2,3,4,5,6,7]输出[1,#,2,3,#,4,5,6,7,#]解释给定二叉树如图 A 所示你的函数应该填充它的每个 next 指针以指向其下一个右侧节点如图 B 所示。序列化的输出按层序遍历排列同一层节点由 next 指针连接# 标志着每一层的结束。
题眼二叉树的层序遍历满二叉树
思路一般 层序遍历的基础上将每层的节点除最后一个外的next值指向下一个节点
class Node:def __init__(self, val0, leftNone, rightNone, nextNone):self.val valself.left leftself.right rightself.next nextdef buildBinartTree(nums: List[Union[int]]) - Optional[Node]:if len(nums) 0:return []if len(nums) 1:return Node(nums[0])# 1、转换为顺序存储tmpTree []for n in nums:tmpTree.append(Node(n))root tmpTree[0]# 2、转换为链式存储parent, child 0, 1while child len(tmpTree):tmpTree[parent].left tmpTree[child] # 满二叉树左孩子一定有效child 1tmpTree[parent].right tmpTree[child] # 满二叉树右孩子一定存在且有效child 1parent 1return rootclass Solution:def connect(self, root: Optional[Node]) - Optional[Node]:# 情况1、树为空if root None:return root# 情况2、树不为空que deque()que.append(root)while len(que) 0:size len(que)pre Nonefor i in range(size):node que.popleft()if i 0: # 记录每层第一个节点为prepre nodeelse: # 从每层第二个节点开始都要给pre的next指针赋值pre.next nodepre nodeif node.left ! None:que.append(node.left)if node.right ! None:que.append(node.right)return rootif __name__ __main__:while True:try:in_line input().strip().split()[1].strip()[1: -1]nums []if in_line ! :for n in in_line.split(,):nums.append(int(n))print(nums)except EOFError:break117. 填充每个节点的下一个右侧节点指针 II 一般 层序遍历的基础上将每层的节点除最后一个外的next值指向下一个节点 from typing import List, Union, Optional
from collections import deque117. 填充每个节点的下一个右侧节点指针 II
给定一个二叉树
struct Node {int val;Node *left;Node *right;Node *next;
}
填充它的每个 next 指针让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点则将 next 指针设置为 NULL。
初始状态下所有next 指针都被设置为 NULL。
示例 1:输入root [1,2,3,4,5,null,7]输出[1,#,2,3,#,4,5,7,#]解释给定二叉树如图 A 所示你的函数应该填充它的每个 next 指针以指向其下一个右侧节点如图 B 所示。序列化输出按层序遍历顺序由 next 指针连接# 表示每层的末尾。
题眼二叉树的层序遍历注意不是满二叉树
思路一般 层序遍历的基础上将每层的节点除最后一个外的next值指向下一个节点
class Node:def __init__(self, val0, leftNone, rightNone, nextNone):self.val valself.left leftself.right rightself.next nextdef buildBinaryTree(nums: List[Union[int, str]]) - Optional[Node]:if len(nums) 0:return Noneif len(nums) 1:return Node(nums[0])# 1、转换为顺序存储tmpTree []for n in nums:if n ! null:tmpTree.append(Node(n))else:tmpTree.append(None)root tmpTree[0]# 2、转换为链式存储parent, child 0, 1while child len(tmpTree):if tmpTree[parent] ! None: # 双亲节点有效性判断if tmpTree[child] ! None: # 左孩子节点有效性判断tmpTree[parent].left tmpTree[child]child 1if child len(tmpTree) and tmpTree[child] ! None: # 左孩子节点存在且有效tmpTree[parent].right tmpTree[child]child 1parent 1return rootclass Solution:def connect(self, root: Optional[Node]) - Optional[Node]:# 情况1、树为空if root None:return root# 情况2、树不为空que deque()que.append(root)while len(que) 0:size len(que)pre Nonefor i in range(size):node que.popleft()if i 0: # 记录每层第一个节点为prepre nodeelse: # 从每层第二个节点开始都要给pre的next指针赋值pre.next nodepre nodeif node.left ! None:que.append(node.left)if node.right ! None:que.append(node.right)return rootif __name__ __main__:while True:try:in_line input().strip().split()[1].strip()[1: -1]nums []if in_line ! :for n in in_line.split(,):if n ! null:nums.append(int(n))else:nums.append(n)print(nums)except EOFError:break104. 二叉树的最大深度 一般 层序遍历的基础上输出最大高度值也就是二叉树的高度值 from typing import List, Optional, Union
from collections import deque104. 二叉树的最大深度
给定一个二叉树找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例 1:输入[3,9,20,null,null,15,7]输出3
题眼二叉树的层序遍历
思路一般 层序遍历的基础上输出最大高度值
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightdef buildBinaryTree(nums: List[Union[int, str]]) - Optional[TreeNode]:if len(nums) 0:return Noneif len(nums) 1:return TreeNode(nums[0])# 1、顺序存储tmpTree []for n in nums:if n ! null:tmpTree.append(TreeNode(n))else:tmpTree.append(None)root tmpTree[0]# 2、链式存储parent, child 0, 1while child len(tmpTree):if tmpTree[parent] ! None: # 双亲结点有效if tmpTree[child] ! None: # 左孩子节点有效tmpTree[parent].left tmpTree[child]child 1 # 指向右孩子if child len(tmpTree) and tmpTree[child] ! None: # 右孩子存在且有效tmpTree[parent].right tmpTree[child]child 1 # 指向下一个节点的左孩子parent 1return rootclass Solution:def maxDepth(self, root: Optional[TreeNode]) - int:# 情况1、树为空if root None:return 0# 情况2、树不为空result 0que deque()que.append(root)while len(que) 0:size len(que)for _ in range(size):node que.popleft()if node.left ! None:que.append(node.left)if node.right ! None:que.append(node.right)result 1return result# 做完了计算完全二叉树的节点数用了带return的递归法有点感觉了看看能否把这里的迭代法写出来def maxDepthRecursive(self, root: Optional[TreeNode]) - int:# 1、确定函数参数和返回值def maxDepth(node: Optional[TreeNode]) - int:# 2、终止条件if node None:return 0# 3、单次递归的操作leftN maxDepth(node.left) # 左rightN maxDepth(node.right) # 右return max(leftN, rightN) 1 # 中return maxDepth(root)if __name__ __main__:obj Solution()while True:try:in_line input().strip().split()[1].strip()[1: -1]nums []if in_line ! :for n in in_line.split(,):if n ! null:nums.append(int(n))else:nums.append(n)root buildBinaryTree(nums)print(obj.maxDepth(root))except EOFError:break111. 二叉树的最小深度 一般 层序遍历的基础上输出最小高度值第一次遍历到叶子节点的时候 from typing import List, Optional, Union
from collections import deque111. 二叉树的最小深度
给定一个二叉树找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明叶子节点是指没有子节点的节点。
示例 1:输入root [3,9,20,null,null,15,7]输出2
题眼二叉树的层序遍历
思路一般 层序遍历的基础上输出最小高度值第一次遍历到叶子节点的时候
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightdef buildBinaryTree(nums: List[Union[int, str]]) - Optional[TreeNode]:if len(nums) 0:return Noneif len(nums) 1:return TreeNode(nums[0])# 1、顺序存储tmpTree []for n in nums:if n ! null:tmpTree.append(TreeNode(n))else:tmpTree.append(None)root tmpTree[0]# 2、链式存储parent, child 0, 1while child len(tmpTree):if tmpTree[parent] ! None: # 双亲结点有效if tmpTree[child] ! None: # 左孩子节点有效tmpTree[parent].left tmpTree[child]child 1 # 指向右孩子if child len(tmpTree) and tmpTree[child] ! None: # 右孩子存在且有效tmpTree[parent].right tmpTree[child]child 1 # 指向下一个节点的左孩子parent 1return rootclass Solution:def minDepth(self, root: Optional[TreeNode]) - int:# 情况1、树为空if root None:return 0# 情况2、树不为空result 0que deque()que.append(root)while len(que) 0:size len(que)for _ in range(size):node que.popleft()if node.left None and node.right None:return result 1if node.left ! None:que.append(node.left)if node.right ! None:que.append(node.right)result 1return result# 做完了最大深度的递归试试这个最小深度的有陷阱def minDepthRecursive(self, root: Optional[TreeNode]) - int:# 1、确定函数参数和返回值def minD(node: Optional[TreeNode]) - int:# 2、终止条件if node None:return 0# 3、单次递归的操作leftN minD(node.left) # 左rightN minD(node.right) # 右# 当一个左子树为空右不为空这时并不是最低点if node.left None and node.right ! None: # 中return 1 rightN# 当一个右子树为空左不为空这时并不是最低点if node.left ! None and node.right None:return 1 leftNreturn min(leftN, rightN) 1return minD(root)if __name__ __main__:obj Solution()while True:try:in_line input().strip().split()[1].strip()[1: -1]nums []if in_line ! :for n in in_line.split(,):if n ! null:nums.append(int(n))else:nums.append(n)root buildBinaryTree(nums)print(obj.minDepth(root))except EOFError:break559. N 叉树的最大深度 一般 层序遍历的基础上遍历children部分 from typing import List, Optional, Union
from collections import deque559. N 叉树的最大深度
给定一个 N 叉树找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示每组子节点由空值分隔请参见示例。示例 1:输入root [1,null,3,2,4,null,5,6]输出3
题眼二叉树的层序遍历
思路一般 层序遍历的基础上遍历children部分
class Node:def __init__(self, valNone, childrenNone):self.val valself.children childrenclass Solution:def maxDepth(self, root: Optional[Node]) - int:# 情况1、树为空if root None:return 0# 情况2、树不为空result 0que deque()que.append(root)while len(que) 0:size len(que)for _ in range(size):node que.popleft()if node.children ! None:for child in node.children:que.append(child)result 1return result
