Binary Tree Traversal 二叉树遍历。
前序、中序、后序遍历用到的数据结构都是栈，使用 Python 的 list 来表示栈，有 append() 和 pop() 方法，都是 O(1) 时间。需要注意的是 list 的带参数的 pop(i) 复杂度是 O(n) 。（所以一般如果要用队列的话最好不要用 list 而是用 collections.deque() 的 append() 和 popleft() 来达到 O(1) 。）
前序遍历
LeetCode 模板题：144. 二叉树的前序遍历
顺序是根左右。
递归版：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root: return []
return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)迭代算法的思路是使用一个栈，每次操作从栈顶弹出一个结点来操作，把结点的值放到结果列表中，再依次压入右结点、左结点。
迭代版：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root: return []
ans = []
stk = [root]
while stk:
node = stk.pop()
ans.append(node.val)
if node.right: stk.append(node.right)
if node.left: stk.append(node.left)
return ans中序遍历
LeetCode 模板题：94. 二叉树的中序遍历
顺序是左根右。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root: return []
return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)迭代算法的思路是从根节点开始，将每个考察到的结点压入栈中，然后走向他的左结点，直到左节点为空时停止，弹出栈顶的结点并将这个结点的值放到结果列表中，之后考察其右节点，继续循环。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root: return []
ans, stk, node = [], [], root
while node or stk:
while node:
stk.append(node)
node = node.left
node = stk.pop()
ans.append(node.val)
node = node.right
return ans中序遍历的这种写法很容易推广到前序和后序，之后会说这样的统一写法。
后序遍历
LeetCode 模板题：145. 二叉树的后序遍历
顺序是左右根。
递归版：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root: return []
return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]迭代算法的思路有两种。
一种是观察后序遍历和先序遍历的联系，后序是左右根，先序是根左右，可以很轻易的稍微改一改先序的程序，使之输出根右左，然后把结果反转一下就是最终结果左右根。
另一种是记录之前访问到的最前面的右结点 lastVisit ，访问到一个结点时，如果上一个访问到的就是这个结点的右结点，则可以把这个结点的值放入结果列表，并且更新栈和 lastVisit 。如果不是，则访问它的右结点即可。
下面分别是这两种方法。反转根右左：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root: return []
ans = []
stk = [root]
while stk:
node = stk.pop()
ans.append(node.val)
if node.left: stk.append(node.left)
if node.right: stk.append(node.right)
return ans[::-1]记录上一个右结点：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root: return []
ans = []
stk = []
node = lastVisit = root
while node or stk:
while node:
stk.append(node)
node = node.left
if stk[-1].right and stk[-1].right != lastVisit:
node = stk[-1].right
else:
ans.append(stk[-1].val)
lastVisit = stk[-1]
stk.pop()
return ans前序中序后序统一写法
话不多说，直接把代码放到一起。
前序遍历：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root: return []
ans, stk, node = [], [], root
while node or stk:
while node:
ans.append(node.val)
stk.append(node)
node = node.left
node = stk.pop()
node = node.right
return ans中序遍历：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root: return []
ans, stk, node = [], [], root
while node or stk:
while node:
stk.append(node)
node = node.left
node = stk.pop()
ans.append(node.val)
node = node.right
return ans后序遍历：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root: return []
ans, stk, node = [], [], root
while node or stk:
while node:
ans.append(node.val)
stk.append(node)
node = node.right
node = stk.pop()
node = node.left
return ans[::-1]三种算法都可以用相似的方式实现出来，这就是前序中序后序统一写法，方便记忆。