94. Binary Tree Inorder Traversal
Level: medium
Tag: tree, stack, hash table
Question
Given a binary tree, return the inorder traversal of its nodes' values.
Example 1
Given binary tree [1,null,2,3],
1
\
2
/
3
return [1,3,2]
Solution 1: 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]
"""
ret = []
self.dps(root, ret)
return ret
def dps(self, root, ret):
"""
:type root: TreeNode
: ret: List[int]
:rtype List[int]
"""
if root:
self.dps(root.left, ret)
ret.append(root.val)
self.dps(root.right, ret)
Solution 2: iteratively (my solution)
use stack to store right child, node value, and left child repeatedly. When node value is popped out, add to result, otherwise repeat.
# 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 = [root]
ret = []
while stack:
node = stack.pop()
if type(node) == int:
ret.append(node)
elif node:
stack.append(node.right)
stack.append(node.val)
stack.append(node.left)
return ret
Another version, popular online
Idea: 假设树为:
1
/ \
2 3
/ \ / \
4 5 6 7
我们使用一个栈来解决问题。步骤如下:
一,我们将根节点1入栈,如果有左孩子,依次入栈,那么入栈顺序为:1,2,4。由于4的左子树为空,停止入栈,此时栈为{1,2,4}。
二,此时将4出栈,并遍历4,由于4也没有右孩子,那么根据中序遍历的规则,我们显然应该继续遍历4的父亲2,情况是这样。所以我们继续将2出栈并遍历2,2存在右孩子,将5入栈,此时栈为{1,5}。
三,5没有孩子,则将5出栈并遍历5,这也符合中序遍历的规则。此时栈为{1}。
四,1有右孩子,则将1出栈并遍历1,然后将右孩子3入栈,并继续以上三个步骤即可。
栈的变化过程:{1}->{1,2}->{1,2,4}->{1,2}->{1}->{1,5}->{1}->{}->{3}->{3,6}->{3}->{}->{7}->{}。
# 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 = []
ret = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
ret.append(node.val)
node = node.right
return ret