问题描述
94 Given a binary tree, return the inorder traversal of its nodes' values.
144 Given a binary tree, return the preorder traversal of its nodes' values.
145 Given a binary tree, return the postorder traversal of its nodes' values.
Note: Recursive solution is trivial, could you do it iteratively?
问题分析
递归的二叉树遍历很简单，只要有递归概念的人都能写，而非递归写法就需要好好想一下了，而且中序、前序、后续遍历各有不同。将递归算法改为非递归算法的核心就是使用栈。
- 前序遍历 前序遍历是三种遍历里最简单的了，因为每次都先访问根节点然后访问左右子树，因此根节点信息不需要保存。遍历操作为：访问根节点->如果有右孩子将右孩子入栈->如果有左孩子将做孩子入栈->如果栈非空，取栈顶元素作为根节点重复遍历操作。
- 中序遍历 中序遍历的思想是：沿着根节点的左孩子一路走下去并将路过的节点入栈，当左孩子为空时，对栈进行pop操作，访问该节点，然后将其右孩子作为根节点重复遍历操作。
- 后序遍历 后续遍历比较复杂的地方在于，它需要记录一个节点的左右子树是否都被访问过，如果都被访问过才能访问该节点。因此在一个节点出栈时，若其flag为False，表示其左右子树还未被访问，将其flag改为True重新入栈，并将其右孩子、左孩子依次入栈；若出栈节点flag为True，表示可以访问它，因此对其进行访问然后继续出栈和遍历操作。
AC代码
二叉树节点定义
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
前序遍历
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root == None:
return []
stack = [root]
rst = []
while len(stack) != 0:
p = stack.pop()
rst.append(p.val)
if p.right:
stack.append(p.right)
if p.left:
stack.append(p.left)
return rst
中序遍历
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root is None:
return []
stack = []
rst = []
p = root
while True:
while p != None:
stack.append(p)
p = p.left
p = stack.pop()
rst.append(p.val)
p = p.right
if len(stack) == 0 and p == None:
break
return rst
后序遍历
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root is None:
return []
stack = [(root, False)]
rst = []
while stack:
p, flag = stack.pop()
if flag:
rst.append(p.val)
continue
else:
stack.append((p, True))
if p.right:
stack.append((p.right, False))
if p.left:
stack.append((p.left, False))
return rst
