Extremely Simple. Morris Traversal. Pre/In/Post Order Summary.
There are a lot of introductions about how Morris Traversal works. It is a beautiful algorithm which takes only O(1) space complexity while still maintaining O(
There are a lot of introductions about how Morris Traversal works. It is a beautiful algorithm which takes only O(1) space complexity while still maintaining O(n) time complexity. Here I summarized how Morris Traversal is implemented w.r.t. all three orders. \n\n**Pre-Order:**\n```\ndef preorderTraversal(self, root: TreeNode) -> List[int]:\n       \n\tres = []\n\n\twhile root:\n\t\tif root.left:\n\t\t\ttemp = root.left\n\t\t\twhile temp.right and temp.right != root:\n\t\t\t\ttemp = temp.right\n\t\t\tif not temp.right:\n\t\t\t\tres.append(root.val) \n\t\t\t\ttemp.right = root\n\t\t\t\troot = root.left\n\t\t\telse:\n\t\t\t\ttemp.right = None \n\t\t\t\troot = root.right\n\t\telse:\n\t\t\tres.append(root.val)\n\t\t\troot = root.right\n\n\treturn res\n```\n**In-Order**: \n\nCompared to Pre-Order implementation, the change is just one line as maked "***"\n```\ndef inorderTraversal(self, root: TreeNode) -> List[int]:\n  \n\tres = []\n\n\twhile root:\n\t\tif root.left:\n\t\t\ttemp = root.left\n\t\t\twhile temp.right and temp.right != root:\n\t\t\t\ttemp = temp.right\n\t\t\tif not temp.right:\n\t\t\t\ttemp.right = root\n\t\t\t\troot = root.left\n\t\t\telse:\n\t\t\t\tres.append(root.val)    # ***\n\t\t\t\ttemp.right = None\n\t\t\t\troot = root.right\n\t\telse:\n\t\t\tres.append(root.val)\n\t\t\troot = root.right\n\n\treturn res\n```\n**Post-Order:**\n\nI saw many implementations for the Post-Order to be very complex and hard to remember. Here I provide a simple version. It is very similar to the pre-order one, except that now we are doing everything reversely. By this I mean we go along the direction of right child and link the leftmost child on the right sub tree to the root. Then we leftappend the val to the result. \n\nTHAT`S IT!!\n```\ndef postorderTraversal(self, root: TreeNode) -> List[int]:\n\t\n\tres = deque()\n\n\twhile root:\n\t\tif root.right:\n\t\t\ttemp = root.right\n\t\t\twhile temp.left and temp.left != root:\n\t\t\t\ttemp = temp.left\n\t\t\tif not temp.left:\n\t\t\t\tres.appendleft(root.val)\n\t\t\t\ttemp.left = root\n\t\t\t\troot = root.right\n\t\t\telse:\n\t\t\t\ttemp.left = None\n\t\t\t\troot = root.left\n\t\telse:\n\t\t\tres.appendleft(root.val)\n\t\t\troot = root.left\n\n\treturn res\n```\n\nHope you like it. Cheers.
[]