morris traversal
using stack
# 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 root==None: return []
res=[]
stack=[]
curr=root
stack.append(curr)
while stack:
#loop and put all the left node in the stack, until there is no more left node
while curr and curr.left:
stack.append(curr.left)
curr=curr.left
#pop the left most node , and add to result
curr=stack.pop()
res.append(curr.val)
#traverse the right node
curr=curr.right
if curr:stack.append(curr)
return res
