Follow tutorial 代码随想录 binary tree
The most subtle algorithm here is we use size and for loop inside single while loop, we achieved traverse one layer with one for loop, if we add some line before, after, in the for loop, it is easy to achieve other functions
the original template is:
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
ans = []
queue = deque()
if root is None:
return ans
queue.append(root)
while queue: # 一次循环遍历完一层
size = len(queue)
layer = []
for i in range(size):
top = queue.popleft()
layer.append(top.val)
if top.left is not None:
queue.append(top.left)
if top.right is not None:
queue.append(top.right)
ans.append(layer)
return ansif we need bottom-up, after put every layer in a list, use the reverse() function
107. 二叉树的层序遍历 II - 力扣（LeetCode）
the document is here:
5. Data Structures — Python 3.14.2 documentation
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
ans = []
queue = deque()
if root is None:
return ans
queue.append(root)
while queue:
size = len(queue)
layer = []
for i in range(size):
top = queue.popleft()
layer.append(top.val)
if top.left is not None:
queue.append(top.left)
if top.right is not None:
queue.append(top.right)
ans.append(layer)
ans.reverse()
return ans
when we traverse to the last element in each row, count it to the ans
just use template
use a for loop to traverse every children
use template
515. 在每个树行中找最大值 - 力扣（LeetCode）
like threaded binary tree, use a pre to record, let pre.next = top
the boundary question:
if pre is None
how to deal with the last node in each line
we solve them with special check
if and only if we meet the first node in each node, the pre == None, so just skip
"""
# Definition for a Node.
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
if root is None:
return root
queue = deque([root])
while queue:
size = len(queue)
pre = None
for i in range(size):
top = queue.popleft()
if top.left is not None:
queue.append(top.left)
if top.right is not None:
queue.append(top.right)
if pre is not None: # the first element in this row
pre.next = top
pre = top
if i == size - 1:
top.next = None
return root
116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）
the variables in python only has scope in module, function, file; variable defined in an if statement is avaiable outside if statement
abandon the bad habit to use flag as a event sign