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 Pre-order Traversal.
Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
Output: [1,2,3]
We have to put the values of Input in Pre-order, which is root -> left -> right
.
Approach
To solve the problem with Morris Traversal, we have to follow the four steps below.
- go one step left if possible and then go right till the end.
- add Node to output and establish the link
predecessor.right = node
. - When we visit the same predecessor the second time, it already points to the current node, thus we remove the link created at step2 and move to right node with
node = node.right
. - return step1
- note: If the step1 is impossible, add node to output and move right to next node.
Here are the points you should remember.
- Add output when node has no left node or predecessors.right is null.
- when predecessor has no right node, make the link from predecessor to node.
- after making the link from predecessor to node, move the node to left.
- after delete the link from predecessor to node, move the node to right.
Here is the example of the traversal.
Solution: Morris Pre-order Tree Traversal
class Solution:
def preorderTraversal(self, root):
"""
:type root: TreeNode
:type: List[int]
"""
node = root
output = []
while node:
if node.left is None:
output.append(node.val)
node = node.right
else:
predecessor = node.left
while predecessor.right and predecessor.right is not node:
predecessor = predecessor.right
if predecessor.right is None:
output.append(node.val)
predecessor.right = node
node = node.left
else:
predecessor.right = None
node = node.right
return output
Thank you for reading this article!
I always welcome your feedback, question, and idea.
Top comments (0)