94. Binary Tree Inorder Traversal
- Total Accepted: 151532
- Total Submissions: 358835
- Difficulty: Medium
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?
Code (recursive)
# 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 is None: return [] return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
Code (Iterative)
class Solution(object): def inorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if root is None: return [] stk = [] res = [] while stk or root: while root: stk.append(root) root = root.left root = stk.pop() res.append(root.val) root = root.right return res
Idea
At first, I was not sure whether to use a queue or a stack to store the nodes to be traversed. But do remember that it is an in-order traversal therefore you need to always start from the leftmost leaf. Thinking in this way, you will be easier to come to use stack.
Reference: https://discuss.leetcode.com/topic/6478/iterative-solution-in-java-simple-and-readable