Morris algorithm and clean iterative normal algorithm in Python (29ms)

• Morris Algorithm - O(n) time and O(1) space algorithm to traverse the tree

This algorithm is to change the structure of the tree to find the next node to be traverse, the steps are listed below:

1. set curNode to root
2. if `curNode.left` is None, output `curNode.val` and set `curNode` to `curNode.right`
3. if `curNode.left` is not None, find `prevNode` of `curNode` in its left subtree
1. if `prevNode.right` == None, set prevNode.right to curNode
2. if `prevNode.right` == `curNode`, set `prevNode.right` back to None, output `curNode`, and update `curNode` to `curNode.right`
4. loop step 1 and 2 until `curNode` is None

Node: `preNode` of curNode in the Steps refers to the node that is adjacently before `curNode` in the output list of the inorder traversal of the given tree.

``````def inorderTraversal(self, root):
def _findRightmost(root, parent):
tmp = root
while tmp.right and tmp.right != parent:
tmp = tmp.right
return tmp

if not root:    return []
ans = []
curNode = root
while curNode:
if curNode.left:
prevNode = _findRightmost(curNode.left, curNode)
if prevNode.right == curNode:
prevNode.right = None
ans.append(curNode.val)
curNode = curNode.right
else:
prevNode.right = curNode
curNode = curNode.left
else:
ans.append(curNode.val)
curNode = curNode.right
return ans
``````

Clean iterative normal algorithm in Python
`thisNode` stores the node that has not been traversed
`stack` stores the node whose left sub-tree has been or will be traversed.

1. if there is a node that has not been traversed at all, we push it into `stack` and then traverse its left subtree.
2. if there is no node that has not been traversed at all, then we pop one node from the `stack` and then start to traverse its right-subtree.
``````def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
thisNode = root # store the node has not been traversed yet
stack = []      # store the node whose left subtree has been traversed
ans = []
while thisNode or stack:
while thisNode:
stack.append(thisNode)
thisNode = thisNode.left
if stack:
thisNode = stack.pop(-1)
ans.append(thisNode.val)
thisNode = thisNode.right
return ans
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.