# 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?
DFS:
class Solution():
def inorderTraversal(self, root):
res = []
self.inorder(root, res)
return res
def inorder(self, root, res):
if not root:
return
self.inorder(root.left, res)
res.append(root.val)
self.inorder(root.right, res)
Stack ( pop()过 == 访问过 ): Note:stack是反着入栈的。
class Solution():
def inorderTraversal(self, root):
res, stack = [], [(root, False)]
while stack:
root, visited = stack.pop()
if not root:
continue
if visited:
res.append(root.val)
else:
stack.append((root.right, False))
stack.append((root, True))
stack.append((root.left, False))
return res