94. Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].
Note:
Recursive solution is trivial, could you do it iteratively?
Solution: Recursive
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
vals = []
if root:
vals.extend(self.inorderTraversal(root.left))
vals.append(root.val)
vals.extend(self.inorderTraversal(root.right))
return vals
Solution: Iterative
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
vals = []
stack = []
while stack or root:
if root:
stack.append(root)
root = root.left
else:
node = stack.pop()
vals.append(node.val)
root = node.right
return vals