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和當前結(jié)點root井氢，訪問當前結(jié)點
- **只要root的左子樹不為空**，將root入棧岳链，同時root左子樹成為新的當前結(jié)點
- 左子樹為空時花竞，將棧的第一個結(jié)點pop,并且當前結(jié)點設(shè)為pop出來結(jié)點的右子樹
- 循環(huán)上述幾個步驟，直到棧為空
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和當前結(jié)點root
- 只要root的左子樹不為空，將root入棧苗分，同時root左子樹成為新的當前結(jié)點
- 左子樹為空時厌蔽，將棧的第一個結(jié)點pop,同時訪問改pop結(jié)點，并且當前結(jié)點設(shè)為pop出來結(jié)點的右子樹
- 循環(huán)上述幾個步驟摔癣，直到棧為空
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
- 循環(huán)上述操作供填，直到stack1為空
- 最后依次pop stack2中的元素即可得到最終結(jié)果
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
# 維護兩個棧stack1,stack2,將根結(jié)點先進行入棧stack1
# 取出棧頂元素，并壓入stack2
# 同時將棧頂元素的左右子樹依次入stack1
# 循環(huán)上述步驟直到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, 當前結(jié)點root, **前一結(jié)點pre（初始為空）**, 先將root入棧
- 如果當前結(jié)點的左右子樹為空近她，或當前結(jié)點有左子樹或者右子樹，但是左或右子樹已經(jīng)被訪問過膳帕，則可以訪問該結(jié)點
- 如果不是上述情況粘捎，將當前結(jié)點的右孩子和左孩子依次入棧，這樣可以保證每次訪問時危彩，左子樹都先被訪問
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