二叉树遍历总结(未完待续...)
leetcode上对于二叉树遍历有如下几种类型的题目：
Binary Tree Preorder Traversal
Binary Tree Inorder Traversal
Binary Tree Postorder Traversal
1、二叉树前序遍历（递归）：
- 思想：对于前序遍历先遍历根，随后遍历左子树，最后遍历右子树
# 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 preorderTraversal(self, root):
:type root: TreeNode
:rtype: List[int]
return self.preorder(root, [])
def preorder(self, root, res):
# 先遍历根，随后左子树，最后右子树
if root == None:
return res
res.append(root.val)
self.preorder(root.left, res)
self.preorder(root.right, res)
return res
```
#####2、二叉树中序遍历（递归）：
- 思想：先遍历左子树 ，随后遍历根，最后右子树
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]
"""
return self.inorder(root, [])
def inorder(self, root, res):
# 中序遍历，先遍历左子树，然后遍历根，最后是右子树
if root == None:
return res
self.inorder(root.left, res)
res.append(root.val)
self.inorder(root.right, res)
return res
#####3、二叉树后序遍历（递归）：
- 思想：先遍历左子树，随后遍历右子树，最后遍历根
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 postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
return self.postorder(root, [])
def postorder(self, root, res):
# 前序遍历，先遍历左子树，随后是右子树，最后遍历根
if root == None:
return res
self.postorder(root.left, res)
self.postorder(root.right, res)
res.append(root.val)
return res
#####4、二叉树前序遍历（非递归）：
- 维护一个栈stack和当前结点root，访问当前结点
- **只要root的左子树不为空**，将root入栈，同时root左子树成为新的当前结点
- 左子树为空时，将栈的第一个结点pop,并且当前结点设为pop出来结点的右子树
- 循环上述几个步骤，直到栈为空
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res, stack = [],[]
while 1:
while root:
res.append(root.val)
stack.append(root)
root = root.left #左子树成为新的root
if not stack:
# 栈为空返回
return res
root = stack.pop()
root = root.right #左子树为空，开始遍历右子树
#####5、二叉树中序遍历（非递归）：
-维护一个栈stack和当前结点root
- 只要root的左子树不为空，将root入栈，同时root左子树成为新的当前结点
- 左子树为空时，将栈的第一个结点pop,同时访问改pop结点，并且当前结点设为pop出来结点的右子树
- 循环上述几个步骤，直到栈为空
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res,stack = [],[]
while 1:
while root:
stack.append(root) #左子树不为空入栈
root = root.left # 左子树成为新的root
if not stack:
return res
root = stack.pop()
res.append(root.val) #先遍历左子树
root = root.right
#####6.1、二叉树后序遍历（非递归）- two stack：
- 维护两个栈stack1,stack2，将root先入栈stack1
- 栈顶出栈压入stack2, 同时将栈顶元素的左右子树依次压入stack1
- 循环上述操作，直到stack1为空
- 最后依次pop stack2中的元素即可得到最终结果
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
# 维护两个栈stack1,stack2,将根结点先进行入栈stack1
# 取出栈顶元素，并压入stack2
# 同时将栈顶元素的左右子树依次入stack1
# 循环上述步骤直到stack1为空
if not root:
return []
stack1,stack2 = [],[]
stack1.append(root)
while stack1:
root = stack1.pop()
stack2.append(root)
if root.left:
stack1.append(root.left)
if root.right:
stack1.append(root.right)
# return [stack2[i].val for i in range(len(stack2)-1,-1,-1)]
return [root.val for root in stack2[::-1]]
#####6.2、二叉树后序遍历（非递归）- one stack：
- 维护一个栈stack, 当前结点root, **前一结点pre（初始为空）**, 先将root入栈
- 如果当前结点的左右子树为空，或当前结点有左子树或者右子树，但是左或右子树已经被访问过，则可以访问该结点
- 如果不是上述情况，将当前结点的右孩子和左孩子依次入栈，这样可以保证每次访问时，左子树都先被访问
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res, stack, pre = [],[],None
stack.append(root) #根先入栈
if not root:
# root为空
return []
while stack:
# stack 非空
root = stack[-1] # 取栈顶元素
if (root.left == None and root.right == None) or (pre != None and (root.left == pre or root.right == pre)):
res.append(root.val)
stack.pop()
pre = root
else:
if root.right:
stack.append(root.right)
if root.left:
stack.append(root.left)
return res
参考资料：
[1] http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html
