中序遍历：左 -> 中 -> 右
练习地址：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
1、递归法
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
def dfs(self, root, res):
if not root:
return
self.dfs(root.left, res)
res.append(root.val)
self.dfs(root.right, res)
def inorderTraversal(self, root):
res = []
self.dfs(root, res)
return res
if __name__ == '__main__':
# 创建一个二叉树
tree = TreeNode(1)
tree.left = TreeNode(2)
tree.right = TreeNode(3)
tree.left.left = TreeNode(4)
tree.left.right = TreeNode(5)
tree.right.right = TreeNode(6)
# 执行中序遍历
sol = Solution()
print(sol.inorderTraversal(tree)) # [4, 2, 5, 1, 3, 6]2、迭代法
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
def inorderTraversal(self, root):
res = []
stack = []
while root or stack:
while root: # 先遍历完所有左节点，放入栈中
stack.append(root)
root = root.left
root = stack.pop() # 将当前节点出栈
res.append(root.val)
# 将右节点作为根节点重新开始遍历，直到 root 和 栈 都为空为止
root = root.right
return res
if __name__ == '__main__':
# 创建一个二叉树
tree = TreeNode(1)
tree.left = TreeNode(2)
tree.right = TreeNode(3)
tree.left.left = TreeNode(4)
tree.left.right = TreeNode(5)
tree.right.right = TreeNode(6)
# 执行中序遍历
sol = Solution()
print(sol.inorderTraversal(tree)) # [4, 2, 5, 1, 3, 6]3、Morris（莫里斯）遍历法
仔细看代码注释与图解，其实原理很简单。
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
'''
主要思想：从上往下，把每一个节点与其右子树挂到左子树的最右边
该方法相比前两种方法，主要是节省了空间，空间复杂度从O(n)变成了O(1)
'''
class Solution(object):
def inorderTraversal(self, root):
res = []
while root:
if root.left: # 如果当前节点存在左子树，则找到其最右边的子节点
pre = root.left
while pre.right: # 找到其最右边的子节点
pre = pre.right
# 把root赋值给temp，把temp的左子树设为空，挂到最右边那个子节点上去
temp = root
root = root.left # 此时根结点被挂到子树上了，我们要变更根结点了，该操作不能放到 temp.left = None 后面，否则执行 temp.left = None 时 root.left 也会被置为空
temp.left = None
pre.right = temp
else:
res.append(root.val) # 如果当前节点已经是最左边的节点了，则可以输出它的值，并开始遍历右子树了
root = root.right
return res
if __name__ == '__main__':
# 创建一个二叉树
tree = TreeNode(1)
tree.left = TreeNode(2)
tree.right = TreeNode(3)
tree.left.left = TreeNode(4)
tree.left.right = TreeNode(5)
tree.right.left = TreeNode(6)
# 执行中序遍历
sol = Solution()
print(sol.inorderTraversal(tree)) # [4, 2, 5, 1, 6, 3]