Traverse Binary Trees
DFS
Preorder
Recursion
def preorder(root):
if not root:
return
print(root.val)
preorder(root.left)
preorder(root.right)
Without recursion
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
stack = []
cur = root
while cur or stack:
if cur:
res.append(cur.val)
stack.append(cur.right)
cur = cur.left
else:
cur = stack.pop()
return res
Inorder
Recursion
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def inorder(root):
if not root:
return
inorder(root.left)
res.append(root.val)
inorder(root.right)
return
inorder(root)
return res
Without recursion
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
stack = []
cur = root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
BFS
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
level = 0
q = deque([root])
while q:
for i in range(len(q)):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
level += 1
return level
Knowledge
题目
Basic Traversal
- 94. Binary Tree Inorder Traversal
- 144. Binary Tree Preorder Traversal
- 145. Binary Tree Postorder Traversal
Traversal
- 114. Flatten Binary Tree to Linked List
- 116. Populating Next Right Pointers in Each Node
- 100. Same Tree
- 112. Path Sum
Operation
Depth
Misc
序列化
Construct Binary Tree by Traversal
- 105. Construct Binary Tree from Preorder and Inorder Traversal
- 106. Construct Binary Tree from Inorder and Postorder Traversal
- 889. Construct Binary Tree from Preorder and Postorder Traversal
解析
NICE binary tree
Question description
A NICE binary tree has the following properties:
- root.val = 0
- If treeNode.val is x and treeNode.left != null, then treeNode.left.val = 2 * x + 1
- If treeNode.val is x and treeNode.right != null, then treeNode.right.val = 2 * x + 2
Now the NICE tree is reseted, which means all treeNode.val have been changed to -1.
Implement the TreeRecover class:
- TreeRecover(TreeNode* root) Initializes the object with a reseted binary tree and recovers it into a NICE binary tree.
- bool query(int target) Returns true if the target value exists in the NICE binary tree
- The key insight is that for a given node value x, its left child is 2 * x + 1 and its right child is 2 * x + 2. This property allows us to determine the path to follow (left or right) for a specific target value without needing to traverse the entire tree.
class TreeNode:
def __init__(self, v):
self.val = v
self.left = None
self.right = None
class Solution:
def check(self, root, target):
found = [False]
def dfs(root, target):
if not root:
return
if root.val == target:
found[0] = True
return
t = target
while True:
if t < root.val:
return
if (root.left and t == root.left.val) or (root.right and t == root.right.val):
if root.left and t == root.left.val:
dfs(root.left, target)
return
if root.right and t == root.right.val:
dfs(root.right, target)
return
reminder = t % 2
if reminder == 0:
t = t / 2 - 1
else:
t = (t - 1) / 2
dfs(root, target)
return found[0]
def construct(self):
root = TreeNode(0)
n1 = TreeNode(1)
n2 = TreeNode(2)
root.left = n1
root.right = n2
n3 = TreeNode(3)
n4 = TreeNode(4)
n1.left = n3
n2.right = n4
n5 = TreeNode(5)
n6 = TreeNode(6)
n2.left = n5
n2.right = n6
n7 = TreeNode(7)
n8 = TreeNode(8)
n3.left = n7
n3.right = n8
n9 = TreeNode(9)
n10 = TreeNode(10)
n4.left = n9
n4.right = n10
n11 = TreeNode(11)
n12 = TreeNode(12)
n5.left = n11
n5.right = n12
n13 = TreeNode(13)
n6.left = n13
return root
if __name__ == '__main__':
s = Solution()
root = s.construct()
print(s.check(root, 13))
Traversal
前序遍历 - BFS - 102. Binary Tree Level Order Traversal
- 用
for i in range(len(queue))来记下当前这一层，一共有多少个不为空的节点，当遍历完他们后，就可以res.append(t)，因为这一层已经遍历完了
# BFS
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
res = []
queue = [root]
while queue:
t = []
for i in range(len(queue)):
n = queue.pop(0)
if n.left:
queue.append(n.left)
if n.right:
queue.append(n.right)
t.append(n.val)
res.append(t)
return res
# Or
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
res = []
queue = [root]
while queue:
t = []
for i in range(len(queue)):
n = queue.pop(0)
if n:
queue.append(n.left)
queue.append(n.right)
t.append(n.val)
if t:
res.append(t)
return res
Ref
前序遍历 DFS/BFS - 104. Maximum Depth of Binary Tree
-
前序遍历
-
类似的问题：如果把根节点看做第 1 层，如何打印出每一个节点所在的层数？
-
def printCurDepth(self, root: Optional[TreeNode]) -> int: def dfs(root, parent_depth): if not root: return 0 cur_depth = parent_depth + 1 print(cur_depth) dfs(root.left, cur_depth) dfs(root.right, cur_depth) dfs(root, 0)
-
# RECURSIVE DFS
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
# ITERATIVE DFS
# use stack for DFS
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
max_depth = 0
stack = [(root, 1)] # (node,depth)
while stack:
node, depth = stack.pop(0)
if node:
max_depth = max(max_depth, depth)
stack.append((node.left, depth + 1))
stack.append((node.right, depth + 1))
return max_depth
# BFS
# use queue for BFS
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
q = []
level = 0
if root:
q.append(root)
while q:
for i in range(len(q)):
node = q.pop(0)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
level += 1 # the node added to the queue is not guaranteed not being None, and thus we could always +1 level
return level
ref
前序遍历 - DFS/BFS - 1448. Count Good Nodes in Binary Tree
# BFS
def goodNodes(self, root: TreeNode) -> int:
res = [0]
def bfs(root):
if not root:
return
queue = [(root, -10000000)] # (node, max_val_in_path)
while queue:
for i in range(len(queue)):
n, max_val_in_path = queue.pop(0)
if n.val >= max_val_in_path:
res[0] += 1
if n.left:
queue.append((n.left, max(max_val_in_path, n.val)))
if n.right:
queue.append((n.right, max(max_val_in_path, n.val)))
bfs(root)
return res[0]
# DFS
def goodNodes(self, root: TreeNode) -> int:
res = [0]
def dfs(root, max_val_in_path):
if not root:
return
if root.val >= max_val_in_path:
res[0] += 1
cur_max = max(max_val_in_path, root.val)
dfs(root.left, cur_max)
dfs(root.right, cur_max)
dfs(root, -100000000)
return res[0]
ref
前序遍历 - 226. Invert Binary Tree
- 前序遍历
后序遍历 - DFS - 543. Diameter of Binary Tree
-
后序遍历
-
类似的问题：打印出每个节点的左右子树各有多少节点？
-
# DFS def printSubTreeNodeNum(self, root: Optional[TreeNode]) -> int: if not root: return 0 left_num = self.printSubTreeNum(root.left) right_num = self.printSubTreeNum(root.right) print("left_sub_tree_node_num:", left_num) print("right_sub_tree_node_num:", right_num) return left_num + right_num + 1
-
# DFS
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
res = [0]
def dfs(root):
if not root:
return 0
left = dfs(root.left)
right = dfs(root.right)
res[0] = max(res[0], left + right)
return max(left, right) + 1
dfs(root)
return res[0]
Ref
前序遍历 BFS - 199. Binary Tree Right Side View
# DFS
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
res = []
def bfs(root):
if not root:
return
queue = [root]
while queue:
t = len(queue) - 1
for idx in range(len(queue)):
n = queue.pop(0)
if idx == t:
res.append(n.val)
if n.left:
queue.append(n.left)
if n.right:
queue.append(n.right)
bfs(root)
return res
ref
114. Flatten Binary Tree to Linked List
116. Populating Next Right Pointers in Each Node
# BFS with stack
# time: O(n)
# address: O(n)
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
if not root:
return None
queue = [root]
while queue:
t = None
for i in range(len(queue)):
node = queue.pop(0)
if node.left and node.right:
queue.append(node.left)
queue.append(node.right)
if t:
t.next = node
t = node
return root
# BFS without stack
# time: O(n)
# address: O(1)
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
if not root:
return None
cur = root
left = root.left
while cur and left: # go bottom
next_level_cur = cur.left
while cur: # go right
left.next = cur.right
if cur.next:
cur.right.next = cur.next.left
cur = cur.next
if cur:
left = cur.left
cur = next_level_cur
left = next_level_cur.left
return root
ref
构造 Binary Tree
105. Construct Binary Tree from Preorder and Inorder Traversal
- 如果 len(preorder) == 0，直接不需要构造Tree
- 如果 len(preorder) >0，root 节点一定是preorder[0]，因为先序遍历的规律就是先访问 root 节点
- 然后在中序遍历的结果中，找到这个 root节点的索引位置，在中序遍历中，该 root节点左边的那些节点，就是该 root 节点的左子树的节点，因为中序遍历的规律就是访问完左子树后，才访问 root 节点
- 又因为中序遍历的规律就是访问完 root 节点后，才访问右子树，所以root 节点后的那些节点，就是该 root 节点的右子树的节点
- 因为无论是前序遍历还是中序遍历，都是最后访问右子树，所以对于中序遍历和前序遍历，访问完 root 节点后要访问的节点都是属于右子树的节点
- 递归
preorder: [3 9 20 15 7]
inorder: [9 3 15 20 7]
-> 说明 root 节点是 3
-> 去 inorder 中，找到 root 节点的索引，即 1
-> 所以 inorder[:(1)] 是左子树的 inorder
-> 左子树的 preorder 是 preorder[1: (1) + 1]
-> 右子树的 inorder 是 inorder[(1) + 1:]
-> 右子树的 preorder 是 preorder[(1) + 1: ]
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if len(preorder) == 0:
return None
v = preorder[0]
parent = TreeNode(v)
inorder_spliter_idx = inorder.index(v)
left_preorder = preorder[1:inorder_spliter_idx + 1]
left_inorder = inorder[:inorder_spliter_idx]
parent.left = self.buildTree(left_preorder, left_inorder)
right_preorder = preorder[inorder_spliter_idx + 1:]
right_inorder = inorder[inorder_spliter_idx + 1:]
parent.right = self.buildTree(right_preorder, right_inorder)
return parent
ref
106. Construct Binary Tree from Inorder and Postorder Traversal
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
if not inorder:
return None
root_val = postorder[-1]
root = TreeNode(root_val)
inorder_splitter_idx = inorder.index(root_val)
root.left = self.buildTree(inorder[:inorder_splitter_idx], postorder[:inorder_splitter_idx])
root.right = self.buildTree(inorder[inorder_splitter_idx + 1:],
postorder[inorder_splitter_idx:len(postorder) - 1])
return root
889. Construct Binary Tree from Preorder and Postorder Traversal
def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
preorder_splitter_idx = 0
preorder_set = set()
postorder_set = set()
for idx in range(1, len(preorder)):
preorder_set.add(preorder[idx])
postorder_set.add(postorder[idx - 1])
if preorder_set == postorder_set:
preorder_splitter_idx = idx
break
root.left = self.constructFromPrePost(preorder[1:preorder_splitter_idx + 1], postorder[0:preorder_splitter_idx])
root.right = self.constructFromPrePost(preorder[preorder_splitter_idx + 1:],
postorder[preorder_splitter_idx:len(postorder) - 1])
return root
序列化
比如说，如果给你一棵二叉树的前序遍历结果，你是否能够根据这个结果还原出这棵二叉树呢？
答案是也许可以，也许不可以，具体要看你给的前序遍历结果是否包含空指针的信息。如果包含了空指针，那么就可以唯一确定一棵二叉树，否则就不行。
举例来说，如果我给你这样一个不包含空指针的前序遍历结果 [1,2,3,4,5]，那么如下两棵二叉树都是满足这个前序遍历结果的：
所以给定不包含空指针信息的前序遍历结果，是不能还原出唯一的一棵二叉树的。
但如果我的前序遍历结果包含空指针的信息，那么就能还原出唯一的一棵二叉树了。比如说用 # 表示空指针，上图左侧的二叉树的前序遍历结果就是 [1,2,3,#,#,4,#,#,5,#,#]，上图右侧的二叉树的前序遍历结果就是 [1,2,#,3,#,#,4,5,#,#,#]，它俩就区分开了。
那么估计就有聪明的小伙伴说了：东哥我懂了，甭管是前中后序哪一种遍历顺序，只要序列化的结果中包含了空指针的信息，就能还原出唯一的一棵二叉树了。
首先要夸一下这种举一反三的思维，但很不幸，正确答案是，即便你包含了空指针的信息，也只有前序和后序的遍历结果才能唯一还原二叉树，中序遍历结果做不到。
本文后面会具体探讨这个问题，这里只简单说下原因：因为前序/后序遍历的结果中，可以确定根节点的位置，而中序遍历的结果中，根节点的位置是无法确定的。
更直观的，比如如下两棵二叉树显然拥有不同的结构，但它俩的中序遍历结果都是 [#,1,#,1,#]，无法区分：
说了这么多，总结下结论，当二叉树中节点的值不存在重复时：
-
如果你的序列化结果中不包含空指针的信息，且你只给出一种遍历顺序，那么你无法还原出唯一的一棵二叉树。
-
如果你的序列化结果中不包含空指针的信息，且你会给出两种遍历顺序，那么按照前文 东哥手把手带你刷二叉树（构造篇） 所说，分两种情况：
- 如果你给出的是前序和中序，或者后序和中序，那么你可以还原出唯一的一棵二叉树。
- 如果你给出前序和后序，那么你无法还原出唯一的一棵二叉树。
-
如果你的序列化结果中包含空指针的信息，且你只给出一种遍历顺序，也要分两种情况：
- 如果你给出的是前序或者后序，那么你可以还原出唯一的一棵二叉树。
- 如果你给出的是中序，那么你无法还原出唯一的一棵二叉树。
Ref
297. Serialize and Deserialize Binary Tree
class Codec:
def serialize(self, root):
res = []
def dfs(node):
if not node:
res.append("N")
return
res.append(str(node.val))
dfs(node.left)
dfs(node.right)
dfs(root)
return ",".join(res)
def deserialize(self, data):
vals = data.split(",")
self.i = 0
def dfs():
if vals[self.i] == "N":
self.i += 1
return None
node = TreeNode(int(vals[self.i]))
self.i += 1
node.left = dfs()
node.right = dfs()
return node
return dfs()
ref
- https://www.youtube.com/watch?v=u4JAi2JJhI8
- https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-66994/dong-ge-da-d14d3/
652. Find Duplicate Subtrees
- 用 DFS 来序列化一个tree，且配合一个hashmap 来判断是否duplicate
def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
key_to_nodes_map = {}
res = [] # space: O(n2)
def dfs(root):
if not root:
return "null"
k = ",".join([str(root.val), dfs(root.left), dfs(root.right)])
if k not in key_to_nodes_map:
key_to_nodes_map[k] = [root]
else:
if len(key_to_nodes_map[k]) == 1:
res.append(root)
key_to_nodes_map[k].append(root)
return k
dfs(root) # time: O(n)
return res
ref