13.7 Exercises
Basic Difficulty
226. Invert Binary Tree
With a clever use of recursion, you can complete this task in just five lines.
617. Merge Two Binary Trees
Similarly, recursion can easily handle this task.
572. Subtree of Another Tree
This is the sister problem of Symmetric Tree, and the implementation is very similar.
404. Sum of Left Leaves
How can you determine if a node is a left leaf? One feasible approach is to pass an additional parameter to the helper function indicating whether the current node is a left child of its parent.
513. Find Bottom Left Tree Value
What condition must the bottom-left node satisfy? How can we locate it based on this condition?
538. Convert BST to Greater Tree
Try to solve this problem using a specific traversal method, visiting each node exactly once.
235. Lowest Common Ancestor of a Binary Search Tree
Using the unique properties of a BST, this problem can be solved quite easily.
530. Minimum Absolute Difference in BST
Remember the traversal method we discussed for BSTs?
Advanced Difficulty
1530. Number of Good Leaf Nodes Pairs
A variation of problem 543. Pay attention in the helper function: the global variable should be updated based on the number of valid pairs of distances between left and right subtrees, while the return value is the height of all valid leaf nodes (+1) from both subtrees.
889. Construct Binary Tree from Preorder and Postorder Traversal
Given any two traversal results, we can reconstruct the tree structure.
106. Construct Binary Tree from Inorder and Postorder Traversal
Given any two traversal results, we can reconstruct the tree structure.
94. Binary Tree Inorder Traversal
Since preorder, inorder, and postorder traversals are implemented using recursion, and recursion inherently uses a stack, we can always use a stack to implement them.
145. Binary Tree Postorder Traversal
Since preorder, inorder, and postorder traversals are implemented using recursion, and recursion inherently uses a stack, we can always use a stack to implement them.
236. Lowest Common Ancestor of a Binary Tree
Now it’s not a BST but a general binary tree. What should we do?
109. Convert Sorted List to Binary Search Tree
Convert a sorted linked list into a BST. To ensure the BST remains balanced, we need to find the middle point of the list.
897. Increasing Order Search Tree
Flatten a BST into a linked list. Be cautious about the order of pointer manipulations to avoid creating loops.
653. Two Sum IV - Input is a BST
Ah, this problem might trick you.
450. Delete Node in a BST
When you locate the node to delete, consider different cases: whether the node is a leaf, has only one child, or has two children. It’s recommended to reclaim memory at the same time.