# 二叉树的前序、中序、后序、层序以及蛇形遍历的实现方式

## 树节点的定义

```public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;

public TreeNode(int x) {
val = x;
}
}```

• `val`，表示当前节点的值；
• `left`，表示当前节点的左儿子节点；
• `right`，表示当前节点的右儿子节点。

## 二叉树的前序遍历

```给定一个二叉树，返回它的前序遍历。

示例:

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) {
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();
if (curr.right != null) {
stack.push(curr.right);
}
if (curr.left != null) {
stack.push(curr.left);
}
}
return ans;
}
}```

## 二叉树的中序遍历

```给定一个二叉树，返回它的中序遍历。

1
\
2
/
3

### 递归

```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);
}
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();
curr = curr.right;
}
return ans;
}
}```

## 二叉树的后序遍历

```给定一个二叉树，返回它的后序遍历。

1
\
2
/
3

### 递归

```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);
}
}
}
}```

### 迭代

```class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
if (root == null) return ans;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode curr = stack.pop();
if (curr.left != null) {
stack.push(curr.left);
}
if (curr.right != null) {
stack.push(curr.right);
}
}
return ans;
}
}```

## 二叉树的层序遍历

```给你一个二叉树，请你返回其按层序遍历得到的节点值。

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) {
}
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;
int level = 0;
while (!queue.isEmpty()) {
int levelLength = queue.size();
for (int i = 0; i < levelLength; ++i) {
TreeNode node = queue.remove();
if (node.left != null) {
}
if (node.right != null) {
}
}
level++;
}
return ans;
}
}```

## 二叉树的蛇形遍历

```给定一个二叉树，返回其节点值的蛇形层次遍历，蛇形层次遍历也称为锯齿形层次遍历。

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> collection = ans.get(level);
if (level % 2 == 0) {
} else {
}
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;
boolean isOrderLeft = true;
while (nodeQueue.size() > 0) {
TreeNode currNode = nodeQueue.pollFirst();
if (currNode != null) {
if (isOrderLeft) {
} else {
}
if (currNode.left != null) {
}
if (currNode.right != null) {
}
} else {
if (nodeQueue.size() > 0) {
}
isOrderLeft = !isOrderLeft;
}
}
return ans;
}
}```

## 总结

• 递归
• 迭代

• 在递归实现中，我们一般需要借助`helper`函数来实现递归的形式；
• 在迭代实现中，我们一般需要借助`Stack``Queue`的特性来实现特殊的存储需求。

0 条评论

• ### 调度服务 ScheduledExecutorService 经常卡顿问题的排查及解决方法

如上述代码所示，启动 10 个调度线程，延迟 10 秒，开始执行定时逻辑，然后每隔 2 秒执行一次定时任务。定时任务类为TaskWorker，其要做的事就是根据...

• ### 效率编程 之「序列化」

对象序列化提供了一个框架，用来将对象编码成字节流，并从字节流编码中重新构建对象。“将一个对象编码成一个字节流”，称作将该对象序列化；相反的处理过程称为反序列化。...

• ### Guava 指南 之「使用和避免 null」

使用和避免null “null，糟糕透啦！” —— Doug Lea. “我称null为百亿美金的错误！” —— C. A. R. Hoare. 轻...

• ### HDU 4135 Co-prime(容斥原理)

Co-prime Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K ...

• ### ​关关的刷题日记99 – Leetcode 56. Merge Intervals

关关的刷题日记99 – Leetcode 56. Merge Intervals 题目 Given a collection of intervals, mer...

• ### python核心编程2 第五章 练习

5-2 运算符 (a) 写一个函数，计算并返回两个数的乘积 (b) 写一段代码调用这个函数，并显示它的结果

• ### android MediaRecorder实现录屏时带录音功能

最近是不是也会遇到需求中需要用到录屏录音的功能,最近也是遇到的 现在整理完记录一下

• ### Python学习总结__Day1

1、解释型：一边编译一边执行，劣势是运行速度慢，但通过运用PyPy交互解释器（JIT技术）会让python程序执行速度快很多。优势是可移植性强。