94.md

94. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree [1,null,2,3],
   1
    \
     2
    /
   3
return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

my thoughts:

1. use a stack and a pointer, **while pointer, put pointer in stack, move pointer to left, if pointer to None, point to stack.pop() and put pointer in res, move pointer to right repeat**

tricky part is the while to left but if to right.

my solution:

**********40ms
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = []
        cur = root
        res = []
        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            res.append(cur.val)
            cur = cur.right
                
        return res              

my comments:

seems the OJ will append any listNode as an array if it is implemented in the array format

from other ppl's solution:

1. use a flag to mark if the left to the node has been visited (0 or 1), if visited, just chech right, 25ms:
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        stack = [(root, 0)]                     # put root in, when root.left has not been visited
        result = []
        while stack:
            node, flag = stack.pop()            # retrieve the last one seen
            if flag:                            # if this one's left has been visited, put it in res
                result.append(node.val)
                if node.right:                  # if this one has right, submit the .right to be checked next, the .right's left has not been visited
                    stack.append((node.right, 0))
            else:
                stack.append((node, 1))			# if the left of the last one seen has not been visited, let's visit it.
                if node.left:					# the left of the .left has not been visited
                    stack.append((node.left, 0))
        return result