二叉树的前序、中序、后序、层序以及蛇形遍历的实现方式
原创
树节点的定义
首先，给出树节点的定义，方便我们理解下面的算法：
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) {
val = x;
}
}如上述代码所示，二叉树节点定义为TreeNode，其中
val，表示当前节点的值；left，表示当前节点的左儿子节点；right，表示当前节点的右儿子节点。
二叉树的前序遍历
给定一个二叉树，返回它的前序遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]如上述所示，前序遍历的顺序为：根节点、左子树和右子树。
递归
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
helper(root, ans);
return ans;
}
private void helper(TreeNode node, List<Integer> ans) {
if (node != null) {
ans.add(node.val);
if (node.left != null) {
helper(node.left, ans);
}
if (node.right != null) {
helper(node.right, ans);
}
}
}
}迭代
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if (root == null) return ans;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode curr = stack.pop();
ans.add(curr.val);
if (curr.right != null) {
stack.push(curr.right);
}
if (curr.left != null) {
stack.push(curr.left);
}
}
return ans;
}
}二叉树的中序遍历
给定一个二叉树，返回它的中序遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]如上述所示，中序遍历的顺序为：左子树、根节点和右子树。
递归
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
helper(root, ans);
return ans;
}
private void helper(TreeNode node, List<Integer> ans) {
if (node != null) {
if (node.left != null) {
helper(node.left, ans);
}
ans.add(node.val);
if (node.right != null) {
helper(node.right, ans);
}
}
}
}迭代
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
ans.add(curr.val);
curr = curr.right;
}
return ans;
}
}二叉树的后序遍历
给定一个二叉树，返回它的后序遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]如上述所示，后序遍历的顺序为：左子树、右子树和根节点。
递归
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
helper(root, ans);
return ans;
}
private void helper(TreeNode node, List<Integer> ans) {
if (node != null) {
if (node.left != null) {
helper(node.left, ans);
}
if (node.right != null) {
helper(node.right, ans);
}
ans.add(node.val);
}
}
}迭代
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
if (root == null) return ans;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode curr = stack.pop();
ans.addFirst(curr.val);
if (curr.left != null) {
stack.push(curr.left);
}
if (curr.right != null) {
stack.push(curr.right);
}
}
return ans;
}
}二叉树的层序遍历
给你一个二叉树，请你返回其按层序遍历得到的节点值。
示例：
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]如上述所示，层序遍历的顺序为：逐层地，从左到右访问所有节点
递归
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) return ans;
helper(root, ans, 0);
return ans;
}
private void helper(TreeNode node, List<List<Integer>> ans, int level) {
if (ans.size() == level) {
ans.add(new ArrayList<>());
}
ans.get(level).add(node.val);
if (node.left != null) {
helper(node.left, ans, level + 1);
}
if (node.right != null) {
helper(node.right, ans, level + 1);
}
}
}迭代
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) return ans;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int level = 0;
while (!queue.isEmpty()) {
ans.add(new ArrayList<>());
int levelLength = queue.size();
for (int i = 0; i < levelLength; ++i) {
TreeNode node = queue.remove();
ans.get(level).add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
level++;
}
return ans;
}
}二叉树的蛇形遍历
给定一个二叉树，返回其节点值的蛇形层次遍历，蛇形层次遍历也称为锯齿形层次遍历。
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回蛇形层次遍历如下：
[
[3],
[20,9],
[15,7]
]如上述所示，蛇形层次遍历的顺序为：先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行。
递归
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
helper(root, ans, 0);
return ans;
}
private void helper(TreeNode node, List<List<Integer>> ans, int level) {
if (node == null) return;
if (ans.size() <= level) {
List<Integer> newLevel = new LinkedList<>();
ans.add(newLevel);
}
List<Integer> collection = ans.get(level);
if (level % 2 == 0) {
collection.add(node.val);
} else {
collection.add(0, node.val);
}
helper(node.left, ans, level + 1);
helper(node.right, ans, level + 1);
}
}迭代
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) return ans;
LinkedList<TreeNode> nodeQueue = new LinkedList<>();
nodeQueue.addLast(root);
nodeQueue.addLast(null);
LinkedList<Integer> levelList = new LinkedList<>();
boolean isOrderLeft = true;
while (nodeQueue.size() > 0) {
TreeNode currNode = nodeQueue.pollFirst();
if (currNode != null) {
if (isOrderLeft) {
levelList.addLast(currNode.val);
} else {
levelList.addFirst(currNode.val);
}
if (currNode.left != null) {
nodeQueue.addLast(currNode.left);
}
if (currNode.right != null) {
nodeQueue.addLast(currNode.right);
}
} else {
ans.add(levelList);
levelList = new LinkedList<>();
if (nodeQueue.size() > 0) {
nodeQueue.addLast(null);
}
isOrderLeft = !isOrderLeft;
}
}
return ans;
}
}总结
如上述内容所示，对于二叉树的各种遍历形式，我们都给出了两种实现方式，分别为：
- 递归
- 迭代
其中，递归实现较为容易，但迭代实现却有些难度。仔细分析代码，我们会发现：
- 在递归实现中，我们一般需要借助
helper函数来实现递归的形式； - 在迭代实现中，我们一般需要借助
Stack或Queue的特性来实现特殊的存储需求。
虽然递归实现相对简单，但因为递归存在着各种各样的问题，所以我们一般不建议使用递归操作，具体可以参考：
这篇博文。到此，本文就结束了，欢迎大家留言讨论！
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录