基础：
遍历有两种方法，一种是递归，一种是迭代（用栈来实现）。
题目：leetcode144—二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
解答：
方法一:递归
# 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 traverval(self,node,res):
if not node:
return
res.append(node.val)
self.traverval(node.left,res)
self.traverval(node.right,res)
def preorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
self.traverval(root,res)
return res
方法二：迭代
访问：遍历节点（入栈）
处理：将元素放进result数组中
前序遍历：根左右，访问和处理结点的顺序一致，故代码相对简洁
# 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: TreeNode) -> List[int]:
res=[]
if not root:
return res
stack=[root]
while stack:
cur=stack.pop()
res.append(cur.val)
#注意此处要先加入右结点，再加入左节点。这样栈在弹出时，会先弹出左节点
if cur.right:
stack.append(cur.right)
if cur.left:
stack.append(cur.left)
return res
题目二：leetcode145—二叉树的后序遍历
给定一个二叉树，返回它的 后序 遍历。
解答：
方法一：递归
# 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 traverval(self,node,res):
if not node:
return
self.traverval(node.left,res)
self.traverval(node.right,res)
res.append(node.val)
def postorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
self.traverval(root,res)
return res
方法二：迭代：先序遍历是根左右，后续遍历是左右根。
那么我们只需要调整一下先序遍历的代码顺序，就变成根右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，即后续遍历的结果。
# 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: TreeNode) -> List[int]:
res=[]
if not root:
return res
stack=[root]
while stack:
cur=stack.pop()
res.append(cur.val) #处理当前结点
if cur.left: #左
stack.append(cur.left)
if cur.right: #右
stack.append(cur.right)
res=res[::-1]
return res
题目三：leetcode94-二叉树的中序遍历
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
解答：
方法一：递归
# 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 traverval(self,node,res):
if not node:
return
self.traverval(node.left,res)
res.append(node.val)
self.traverval(node.right,res)
def inorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
self.traverval(root,res)
return res
方法二：迭代
# 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 traverval(self,node,res):
if not node:
return
self.traverval(node.left,res)
res.append(node.val)
self.traverval(node.right,res)
def inorderTraversal(self, root: TreeNode) -> List[int]:
res=[]
if not root:
return res
stack=[]
cur=root
while cur or stack:
#先找到最左端的结点
if cur:
stack.append(cur)
cur=cur.left #访问左结点
else:
cur=stack.pop()
res.append(cur.val) #处理当前结点
cur=cur.right #访问右结点
return res