102. 二叉树的层序遍历给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。示例 1输入root [3,9,20,null,null,15,7]输出[[3],[9,20],[15,7]]示例 2输入root [1]输出[[1]]示例 3输入root []输出[]提示树中节点数目在范围 [0, 2000] 内-1000 Node.val 1000实现代码Python:#递归方法# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution(object):deflevelOrder(self,root): :type root: Optional[TreeNode] :rtype: List[List[int]] ifnotroot:return[]levels[]deftranverse(node,level):ifnotnode:returniflen(levels)level:levels.append([])levels[level].append(node.val)ifnode.left:tranverse(node.left,level1)ifnode.right:tranverse(node.right,level1)tranverse(root,0)returnlevels#利用队列实现fromcollectionsimportdeque# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution(object):deflevelOrder(self,root): :type root: Optional[TreeNode] :rtype: List[List[int]] ifnotroot:return[]queuedeque([root])res[]whilequeue:level[]for_inrange(len(queue)):nodequeue.popleft()level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)res.append(level)returnres分析二叉树的层序遍历——广度优先遍历需要借用一个辅助数据结构即队列来实现队列先进先出符合一层一层遍历的逻辑而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。107. 二叉树的层序遍历 II给你二叉树的根节点 root 返回其节点值 自底向上的层序遍历 。 即按从叶子节点所在层到根节点所在的层逐层从左向右遍历示例 1输入root [3,9,20,null,null,15,7]输出[[15,7],[9,20],[3]]示例 2输入root [1]输出[[1]]示例 3输入root []输出[]提示树中节点数目在范围 [0, 2000] 内-1000 Node.val 1000实现代码Python:#队列fromcollectionsimportdeque# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution(object):deflevelOrderBottom(self,root): :type root: Optional[TreeNode] :rtype: List[List[int]] ifnotroot:return[]queuedeque([root])res[]whilequeue:level[]for_inrange(len(queue)):nodequeue.popleft()level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)res.append(level)res.reverse()#反转returnres
力扣刷题——102. 二叉树的层序遍历107. 二叉树的层序遍历 II
102. 二叉树的层序遍历给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。示例 1输入root [3,9,20,null,null,15,7]输出[[3],[9,20],[15,7]]示例 2输入root [1]输出[[1]]示例 3输入root []输出[]提示树中节点数目在范围 [0, 2000] 内-1000 Node.val 1000实现代码Python:#递归方法# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution(object):deflevelOrder(self,root): :type root: Optional[TreeNode] :rtype: List[List[int]] ifnotroot:return[]levels[]deftranverse(node,level):ifnotnode:returniflen(levels)level:levels.append([])levels[level].append(node.val)ifnode.left:tranverse(node.left,level1)ifnode.right:tranverse(node.right,level1)tranverse(root,0)returnlevels#利用队列实现fromcollectionsimportdeque# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution(object):deflevelOrder(self,root): :type root: Optional[TreeNode] :rtype: List[List[int]] ifnotroot:return[]queuedeque([root])res[]whilequeue:level[]for_inrange(len(queue)):nodequeue.popleft()level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)res.append(level)returnres分析二叉树的层序遍历——广度优先遍历需要借用一个辅助数据结构即队列来实现队列先进先出符合一层一层遍历的逻辑而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。107. 二叉树的层序遍历 II给你二叉树的根节点 root 返回其节点值 自底向上的层序遍历 。 即按从叶子节点所在层到根节点所在的层逐层从左向右遍历示例 1输入root [3,9,20,null,null,15,7]输出[[15,7],[9,20],[3]]示例 2输入root [1]输出[[1]]示例 3输入root []输出[]提示树中节点数目在范围 [0, 2000] 内-1000 Node.val 1000实现代码Python:#队列fromcollectionsimportdeque# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, val0, leftNone, rightNone):# self.val val# self.left left# self.right rightclassSolution(object):deflevelOrderBottom(self,root): :type root: Optional[TreeNode] :rtype: List[List[int]] ifnotroot:return[]queuedeque([root])res[]whilequeue:level[]for_inrange(len(queue)):nodequeue.popleft()level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)res.append(level)res.reverse()#反转returnres
