Tree Basic Problems

Problems - Traverse

Problems Solutions Key Points code Complexity
226. Invert Binary Tree 1. Traverse
2. Sub Task		 code
116. Populating Next Right Pointers in Each Node 1. BFS
2. DFS traverse with 3-nary tree		 code
114. Flatten Binary Tree to Linked List 1. Sub Task idea Definition of Recursion function code
257. Binary Tree Paths Traverse + DFS how to record the trace. code
129. Sum Root to Leaf Numbers Traverse + DFS Similar with 257 code
199. Binary Tree Right Side View Traverse + BFS or DFS code
662. Maximum Width of Binary Tree Traverse + BFS code
988. Smallest String Starting From Leaf Traverse + DFS code
1022. Sum of Root To Leaf Binary Numbers Traverse + DFS code
1457. Pseudo-Palindromic Paths in a Binary Tree Traverse + DFS bit operation to check if a path is pseudo-palindromic. refer to the code code
- - - - -

Problems - Sub Tasks

Problems Solutions Key Points code Complexity
105. Construct Binary Tree from Preorder and Inorder Traversal Sub Task code
106. Construct Binary Tree from Inorder and Postorder Traversal Sub Task HashMap to reduce time complexity code
889. Construct Binary Tree from Preorder and Postorder Traversal Sub Task 1. HashMap to reduce time complexity
2. Use slice index		 code
331. Verify Preorder Serialization of a Binary Tree 1. Sub Task
2. Iteration		 1. With Sub Task approach, we actually construct the tree. And need to check every scenarios if the string is valid.
2. With iteration, consider to reduce the space complexity		 code
894. All Possible Full Binary Trees Sub Task How to abstract the Sub Tasks into the left and right child tree? Refer to the code. code
998. Maximum Binary Tree II Sub Task code
1110. Delete Nodes And Return Forest Sub Task How to make sure a node need to collected? code
- - - - -

Problems - BFS

Problems Solutions Key Points code Complexity
102. Binary Tree Level Order Traversal BFS code
107. Binary Tree Level Order Traversal II BFS code
117. Populating Next Right Pointers in Each Node II 1. BFS
2. Pointer Apporached for constant extra space. Refer to the code		 code
662. Maximum Width of Binary Tree 1. BFS
2. DFS		 Record the node index code
515. Find Largest Value in Each Tree Row BFS code
637. Average of Levels in Binary Tree BFS code
958. Check Completeness of a Binary Tree BFS 3 scenarios. Refer to the code code
1161. Maximum Level Sum of a Binary Tree 1. BFS
2. DFS		 With DFS, use list or map? Refer to the code code
1302. Deepest Leaves Sum BFS code
1609. Even Odd Tree BFS code
- - - - -

Problems - Construction

二叉树的构造问题一般都是使用「分解问题」的思路：构造整棵树 = 根节点 + 构造左子树 + 构造右子树。

Problems Solutions Key Points code Comments
654. Maximum Binary Tree 1. Sub Task code
105. Construct Binary Tree from Preorder and Inorder Traversal 1. Sub Task code Complexity analyze
106. Construct Binary Tree from Inorder and Postorder Traversal 1. Sub Task code Similar Complexity as 105
889. Construct Binary Tree from Preorder and Postorder Traversal 1. Sub Task Check if current node only has 1 child code
- - - - -

Complexity Analyse

Pay attention to the left-skewed tree and right-skewed tree

Tree Shape Recursive Calls for Loop Work per Call Total Complexity
Right-Skewed Tree O(n) O(1) O(n)
Left-Skewed Tree O(n) O(n) O(n²)
Balanced Tree O(log n) O(n) per level O(n log n)
Optimized (Hash Map Lookup) Right-Skewed O(n) O(1) O(n)
Optimized (Hash Map Lookup) Left-Skewed O(n) O(1) O(n)
Optimized (Hash Map Lookup) Balanced O(log n) O(1) O(n)

Problems - Serialization

什么样的序列化的数据可以反序列化出唯一的一棵二叉树？

当二叉树中节点的值不存在重复时：

如果序列化结果中不包含空指针，只给出一种遍历顺序，那么无法还原出唯一的一棵二叉树。

如果序列化结果中不包含空指针的信息，且给出两种遍历顺序，分两种情况：

  • 如果给出的是前序和中序，或者后序和中序，那么可以还原出唯一的一棵二叉树。

  • 如果给出前序和后序，那么无法还原出唯一的一棵二叉树。

如果你的序列化结果中包含空指针的信息，且只给出一种遍历顺序，也要分两种情况：

  • 如果给出的是前序或者后序，那么可以还原出唯一的一棵二叉树。

  • 如果给出的是中序，那么无法还原出唯一的一棵二叉树。

Problems Solutions Key Points code Complexity
297. Serialize and Deserialize Binary Tree 1. Sub Task
2. BFS		 1. The return value of traverse function
2. Same approach to deserialize		 code O(N)
- - - - -

Problems - Ancestor Problems

Problems Solutions Key Points code Complexity
236. Lowest Common Ancestor of a Binary Tree 1. post-order DFS
2. Track the path from root to target node and compare the slice		 1. Only 2 situations: one left, on right and one is parent of another
2. The loop order of the track slice		 code
1676. Lowest Common Ancestor of a Binary Tree IV Same as 236 Note: these 2 questions require the node MUST in the tree code
1644. Lowest Common Ancestor of a Binary Tree II Sub Task. Note: p,q NOT necessary int the tree. So, need to make sure EACH node is traversed to check if it exists. So, put logic root.Value == p.Value or root.Value == q.Value to the post-order location code
235. Lowest Common Ancestor of a Binary Search Tree 1.Sub task.
2. Iteration		 1. Utilize the character of BST code 1. O(N), O(N)
2. O(N), O(1)
1650. Lowest Common Ancestor of a Binary Tree III Linked list 1. Check the public node 2 linked list code
1257. Smallest Common Region Same solutions as 1650 code
-

Problems - BST Problems

Problems Solutions Key Points code Comments
108. Convert Sorted Array to Binary Search Tree code
1382. Balance a Binary Search Tree in-order traverse + convert ordered array to BST code
314. Binary Tree Vertical Order Traversal code

BST Problems - Construction

Problems Solutions Key Points code Comments
96. Unique Binary Search Trees DFS post-order How to set memo effectively code
95. Unique Binary Search Trees II DFS post-order Edged case of low > high and low == high code

Reference

  1. https://labuladong.online/algo/data-structure/bst-part3/
  • LC116. Populating Next Right Pointers in Each Node
    • Why the normal traverse approach doesn't work with this problem? O(N), O(1)
    • Util BFS traverse. O(N), O(N)
    • LC117. Populating Next Right Pointers in Each Node II
      • BFS approach. O(N), O(N)
      • BFS approach with cursive. O(N), O(N)
      • Multiple pointers approach & sentinel. O(N), O(Cons). And the approach also work with LC116.
  • LC114. Flatten Binary Tree to Linked List
    • Traverse the tree, construct the link.
    • Flat recursively

Construction

results matching ""

    No results matching ""