二叉树遍历，看完就会了！（上）
大家好呀，我是在爬二叉树的帅蛋。
二叉树遍历的实现历来是面试的高频问题，关于二叉树的前中后序遍历有两种实现方式：递归和非递归。
递归实现起来简单一些，而非递归的实现需要借助之前讲过的【栈】这个数据结构
这两种实现方式都需要蛋粉们牢牢掌握，我们先从简单的开始，先讲递归版的二叉树前中后序遍历。
关于递归，我之前写过一篇很详细的文章：
没看过的蛋粉可以看一下。
说白了递归就是一种循环，一种自己调用自己的循环。
一道题你看能不能用递归实现，需要具备两个条件：
- 问题可以分为多个重复的子问题，子问题仅存在数据规模的差距。
- 存在终止条件。
所以根据条件，对于实现递归，只需要两步：
- 找出重复的子问题（递推公式）。
- 终止条件。
话不多说，赶紧开整。
下面我用三道题来给大家具体讲解二叉树前中后序遍历的递归版。
这篇是我在牛客网连载系列 #帅蛋的数据结构与算法空间#的第 11 篇文章，欢迎大家关注。
也希望大家能够喜欢上帅蛋，多多点赞收藏，记得关注我呀！
二叉树前序遍历（递归版）
给你二叉树根节点 root，返回它节点值的前序遍历。
示例
输入：root = [1,null,2,3]
输出：[1,2,3]
解析
根据上面讲的实现递归的两步来找：
(1) 找出重复的子问题
这个很好找，前序遍历的顺序是：根、左子树、右子树。
对于左子树或者右子树来说，也是同样的遍历顺序。
所以这个重复的子问题就出来了，先取根节点，再遍历左子树，最后遍历右子树。
print(root.val) preOrder(root.left) preOrder(root.right)
(2) 确定终止条件
对于二叉树的遍历来说，想终止，即没东西遍历了，没东西遍历自然就停下来了。
那就是当前的节点是空的，既然是空的那就没啥好遍历。
if root == None:
return 最重要的两点确定完了，那总的代码也就出来了。
代码实现
Python 代码实现
# 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 preOrder(self, root: TreeNode, res):
if root == None:
return
res.append(root.val)
self.preOrder(root.left, res)
self.preOrder(root.right, res)
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
self.preOrder(root, res)
return res Java 代码实现
class Solution {
public void preOrder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
res.add(root.val);
preOrder(root.left, res);
preOrder(root.right, res);
}
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
preOrder(root, res);
return res;
}
} 此解法，由于每个节点被遍历一次，所以时间复杂度为 O(n)。
额外维护了一个 res 列表，空间复杂度为 O(n)。
二叉树中序遍历（递归版）
给你二叉树根节点 root，返回它的中序遍历。
示例
输入：root = [1,null,2,3]
输出：[1,3,2]
解析
同样根据上面讲的实现递归的两步来找：
(1) 找出重复的子问题
中序遍历的顺序是：左子树、根、右子树。
对于左子树、右子树来说，也是同样的遍历顺序。
所以这个重复的子问题就是：先遍历左子树、再取根节点，最后遍历右子树。
inOrder(root.left) print(root.val) inOrder(root.right)
(2) 确定终止条件
和前序遍历相同，就是当前的节点为空，空的没啥好遍历的。
if root == None:
return 最重要的两点确定完了，那总的代码也就出来了。
代码实现
Python 代码实现
# 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 inOrder(self, root:TreeNode, res):
if root == None:
return
self.inOrder(root.left, res)
res.append(root.val)
self.inOrder(root.right, res)
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
self.inOrder(root, res)
return res Java 代码实现
class Solution {
public void inOrder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
inOrder(root.left, res);
res.add(root.val);
inOrder(root.right, res);
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
inOrder(root, res);
return res;
}
} 和前序遍历相同，中序遍历时间复杂度为 O(n)，空间复杂度为 O(n)。
二叉树后序遍历（递归版）
给定一个二叉树，返回它的后序遍历。
示例
输入：root = [1,null,2,3]
输出：[3,2,1]
解析
还是根据上面讲的实现递归的两步来找：
(1) 找出重复的子问题。
后序遍历的顺序是：左子树、右子树、根，对于左子树、右子树来说，也是同样的遍历顺序。
所以这个重复的子问题就是：先遍历左子树、再遍历右子树、再取根节点。
postOrder(root.left) postOrder(root.right) print(root.val)
(2) 确定终止条件。
和前序遍历、中序遍历相同，就是当前的节点为空，空的没啥好遍历的。
if root == None:
return 最重要的两点确定完了，那总的代码也就出来了。
代码实现
Python 代码实现
# 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 postOrder(self, root: TreeNode, res):
if root == None:
return
self.postOrder(root.left, res)
self.postOrder(root.right, res)
res.append(root.val)
def postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
self.postOrder(root, res)
return res Java 代码实现
class Solution {
public void postorder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
postorder(root.left, res);
postorder(root.right, res);
res.add(root.val);
}
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
postorder(root, res);
return res;
}
}
和前序遍历、中序遍历相同，后序遍历时间复杂度为 O(n)，空间复杂度为 O(n)。
好啦，到这递归版的二叉树的前中后序遍历就讲完啦。
是不是蛋粉们觉得很简单？
如果因此你就小看了二叉树遍历，那你就图样图森破，非递归的二叉树遍历还是不那么简单的。
当然啦，我肯定不会说，不那么简单还是简单。
❤️ 欢迎关注我，有问题，找帅蛋，我最看不得别人迷茫！
❤️ 如果你觉得有帮助,希望爱学习的你不要吝啬三连击哟[点赞 + 收藏 + 评论]~
还有小小公众号 【编程文青李狗蛋】，聊聊迷茫吹吹牛皮~
- 数据结构与算法作为计算机学生最重要的课程之一，不管是面试或者考研都是重中之重，不应该让这个成为同学们的困扰。 - 站在初学者的角度，用最直白的图解和最易懂的代码，最大可能摒除不同编程语言的带来的干扰，带你彻底搞定数据结构与算法。 - 本专栏适用于任何想要学习数据结构与算法的未来巨巨~
投递阿里云等公司10个岗位 >
