[Leetcode Solution] Binary Tree Inorder Traversal

Analysis

• It's pretty simply by using recursive way to do in-order traversal of the binary tree
• There are two ways to do it iteratively
• First, using a stack dfs with a state variable for each node to indicate if the left child has been visited. If it is ,then visit this node and then visit the right child sub tree. Else if the left child sub tree has not been visited, set the state variable as visited, and then visit left child sub tree first
• Second traversal iteratively with constant space by using Morris in-order traversal which is a pretty tricky solution. It maintains the traversal order by delicate modify the tree and recover the tree back after traverse. The details can be found here

Note

• If using a stack to store the traversal sequence of DFS, attention should be paid if the back of stack if frequently modified. Because after pop_back or push_back, the stack.back() might not the ones you expected

Code