This is part of my series where I memo learning from LeetCode. If you have better solutions or ideas, please leave a comment!
The pattern of Tree Traversal
Here are three patterns for Tree Traversal.
Each patten has only one order.
- Pre-order Traversal
- root -> left -> right
- In-order Traversal
- left -> root -> right
- Post-order Traversal
- right -> left -> root
Problem
Today's problem is about In-order Traversal.
Given a binary tree, return the inorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
Output: [1,3,2]
We have to put the values of Input in In-order, which is left -> root -> right
.
Approach
To solve the problem with Morris In-order Tree Traversal, we have to follow the rules below.
-
if current has no left child,
- Add current's value to output.
-
current = current.right
.
-
if current has left child,
- make the current the right child of the rightmost node in current's left subtree.
current = current.left
note: Don't forget the original current left to be null to avoid infinite loops in rule.2
Here is the example of the traversal.
Solution: Morris In-order Tree Traversal
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
output = []
current = root
while current is not None:
if current.left is None:
output.append(current.val)
current = current.right
else:
predecessor = current.left
while predecessor.right:
predecessor = predecessor.right
predecessor.right = current
tmp = current
current = current.left
tmp.left = None
return output
Thank you for reading this article!
I always welcome your feedback, question, and idea.
Top comments (0)