# 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 classSolution: defpreorderTraversal(self, root: Optional[TreeNode]) -> List[int]: stack = [(root, False)] if root else [] res = list()
while stack: node, visit_status = stack.pop() if visit_status: res.append(node.val) else: # 按前序遍历,“中左右”,但这里是栈,所以应该是“右左中”;不过,我决定在最后使用反转大法 # 所以这里还是按“中左右”进行入栈 stack.append((node, True)) if node.left: stack.append((node.left, False)) if node.right: stack.append((node.right, False)) res = res[::-1] return res
definorderTraversal(self, root: Optional[TreeNode]) -> List[int]: # res = list() # self.traversal(root, res) # return res
# 迭代 ifnot root: return [] res = list() stack = list() cur = root while cur or stack: # 先一路干到最底层的左子树节点 if cur: stack.append(cur) cur = cur.left # 到达最左节点后,开始处理栈顶节点 else: cur = stack.pop() res.append(cur.val) # 取栈顶元素右节点 cur = cur.right return res
queue = deque() res = list() queue.append(root) while queue: # level记录的是每层的结果 level = list() L = len(queue) # 注意这里的L不会跟着queue增加或减少而变化 for i inrange(L): cur = queue.popleft() level.append(cur.val) if cur.left: queue.append(cur.left) if cur.right: queue.append(cur.right) # 最终将每层的结果汇总到res中 res.append(level)
# 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 from collections import deque classSolution: deflevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: ifnot root: return [] res = list() queue = deque() queue.append(root)
while queue: level_res = list() # 操作位置1 L = len(queue) for i inrange(L): node = queue.popleft() level_res.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) # 操作位置2 (每层的清算) res.append(level_res) return res
# 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 classSolution: defrightSideView(self, root: Optional[TreeNode]) -> List[int]: # 层序遍历,但规则是:只遍历这层最后一个节点 from collections import deque ifnot root: return [] queue = deque() res = list() queue.append(root)
while queue: # level_res其实只要保持一个节点即可 level_res = None L = len(queue) for _ inrange(L): node = queue.popleft() # 用这层新节点替换掉之前的结果,保证level_res只记录当前层最后一个节点 level_res = node.val if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(level_res) return res
while queue: L = len(queue) for i inrange(L): node = queue.popleft() # 如果是当前层最后一个,才记录 if i == L - 1: res.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return res
# 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 classSolution: defaverageOfLevels(self, root: Optional[TreeNode]) -> List[float]: from collections import deque
que = deque() ifnot root: return [] que.append(root) res = [] while que: L = len(que) levelsum = 0 count = 0 for i inrange(L): node = que.popleft() levelsum += node.val count += 1 if node.left: que.append(node.left) if node.right: que.append(node.right) res.append(levelsum/count) return res
""" # Definition for a Node. class Node: def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None): self.val = val self.children = children """
classSolution: deflevelOrder(self, root: 'Node') -> List[List[int]]: from collections import deque que = deque() ifnot root: return [] que.append(root) res = list() while que: L = len(que) levelList = list() for i inrange(L): node = que.popleft() levelList.append(node.val) for eachNode in node.children: que.append(eachNode) res.append(levelList) return res
# 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 classSolution: deflargestValues(self, root: Optional[TreeNode]) -> List[int]: from collections import deque
que = deque() ifnot root: return [] que.append(root) res = [] while que: L = len(que) levelMax = None for i inrange(L): node = que.popleft() if levelMax isNone: levelMax = node.val else: levelMax = max(levelMax, node.val) if node.left: que.append(node.left) if node.right: que.append(node.right) res.append(levelMax) return res
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。
初始状态下,所有 next 指针都被设置为 NULL。
示例 1:
1 2 3
输入:root = [1,2,3,4,5,6,7] 输出:[1,#,2,3,#,4,5,6,7,#] 解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化的输出按层序遍历排列,同一层节点由 next 指针连接,'#' 标志着每一层的结束。
""" # 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 """
classSolution: defconnect(self, root: 'Optional[Node]') -> 'Optional[Node]': from collections import deque
que = deque() ifnot root: return que.append(root)
while que: L = len(que) levelList = list() for i inrange(L): node = que.popleft() levelList.append(node) # 添加下一层到队列 if node.left: que.append(node.left) if node.right: que.append(node.right) # 将这层串起来 for i inrange(len(levelList) - 1): levelList[i].next = levelList[i+1] return root
""" # 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 """
classSolution: defconnect(self, root: 'Optional[Node]') -> 'Optional[Node]': from collections import deque
que = deque() ifnot root: return que.append(root)
while que: L = len(que) nodePrev = None for i inrange(L): node = que.popleft() if nodePrev: nodePrev.next = node nodePrev = node # 添加下一层到队列 if node.left: que.append(node.left) if node.right: que.append(node.right) return root