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:
- set curNode to root
curNode.leftis None, output
curNode.leftis not None, find
curNodein its left subtree
prevNode.right== None, set prevNode.right to curNode
prevNode.rightback to None, output
curNode, and update
- loop step 1 and 2 until
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
Morris Reference: http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html
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.
- if there is a node that has not been traversed at all, we push it into
stackand then traverse its left subtree.
- if there is no node that has not been traversed at all, then we pop one node from the
stackand 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