树的遍历(递归+迭代)

1.相关博客

因为二叉树这种数据结构本身天然的就具有递归的结构,所以面对二叉树问题,使用递归方法解决通常比较简单。

注意:示例代码中的 TreeNode 对象、Node 对象和结构体定义如下:

1
2
3
4
5
6
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Node {
public int val;
public List<Node> children;

public Node() {}

public Node(int _val) {
val = _val;
}

public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
1
2
3
4
5
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
}

2.树的前序遍历

  • 前序遍历也称为先序遍历
  • 遍历过程为:
    • ①访问根结点
    • ②先序遍历其左子树
    • ③先序遍历其右子树
  • 举例:
    • 下图的先序遍历结果为:1、2、3、4、5、6、7、8、9。

Alt text

①二叉树-递归

  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
// 递归函数定义: 前序遍历以root节点为根节点的二叉树
private void traversal(TreeNode root, List list) {
// 递归终止条件
if (root == null) {
return;
}
// 递归过程
// 处理当前节点
list.add(root.val);
// 前序遍历root节点的左子树
traversal(root.left, list);
// 前序遍历root节点的右子树
traversal(root.right, list);
}

public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
traversal(root, list);
return list;
}
}
  • C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 递归函数,returnSize、arr是指针,动态修改。
// 递归函数定义: 前序遍历以root节点为根节点的二叉树
void orderTraversal(struct TreeNode* root, int* returnSize, int* arr) {
// 递归终止条件
if (!root) {
return;
}
// 递归过程
// 处理当前节点
arr[(*returnSize)++] = root->val;
// 前序遍历root节点的左子树
orderTraversal(root->left, returnSize, arr);
// 前序遍历root节点的右子树
orderTraversal(root->right, returnSize, arr);
}

// 统计结点数
int makeSize(struct TreeNode* root) {
if (!root) {
return 0;
}
return makeSize(root->left) + makeSize(root->right) + 1;
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
int size = makeSize(root);
int* arr = (int*)malloc(sizeof(int) * size);
*returnSize = 0;
orderTraversal(root, returnSize, arr);
return arr;
}

②二叉树-迭代

  • 遇到一个节点就访问它,然后把它压入栈中,并去遍历它的左子树。当左子树遍历结束后,弹出栈顶元素,再去先序遍历该节点的右子树。
  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
while (!stack.isEmpty() || root != null) {
// 遇到一个节点就访问它,然后把它压入栈中,并去遍历它的左子树。
while (root != null) {
list.add(root.val);
stack.push(root);
root = root.left;
}
// 当左子树遍历结束后,弹出栈顶元素。
if (!stack.isEmpty()) {
root = stack.pop();
// 再去先序遍历该节点的右子树
root = root.right;
}
}
return list;
}
}
  • C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 统计结点数
int makeSize(struct TreeNode* root) {
if (!root)
return 0;

return makeSize(root->left) + makeSize(root->right) + 1;
}

typedef struct {
struct TreeNode** array;
int top;
} Stack;

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
int size = makeSize(root);
int* arr = (int*)malloc(sizeof(int) * size);
*returnSize = 0;
Stack* s = (Stack*)malloc(sizeof(Stack));
s->array = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * size);
s->top = -1;
while (s->top != -1 || root) {
// 遇到一个节点就访问它,然后把它压入栈中,并去遍历它的左子树。
while (root) {
arr[(*returnSize)++] = root->val;
s->array[++s->top] = root;
root = root->left;
}
// 当左子树遍历结束后,弹出栈顶元素。
if (s->top != -1) {
root = s->array[s->top--];
// 再去先序遍历该节点的右子树
root = root->right;
}
}
return arr;
}

③N叉树-递归

  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
// 递归函数定义: 前序遍历以root节点为根节点的N叉树
private void traversal(Node root, List list) {
// 递归终止条件
if (root == null) {
return;
}
// 递归过程
// 处理当前节点
list.add(root.val);
// 前序遍历root节点的每个子树
for (Node node: root.children) {
traversal(node, list);
}
}
public List<Integer> preorder(Node root) {
List<Integer> list = new ArrayList<Integer>();
traversal(root, list);
return list;
}
}

④N叉树-迭代

  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public List<Integer> preorder(Node root) {
Stack<Node> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
stack.push(root);
while (!stack.isEmpty()) {
root = stack.pop();
list.add(root.val);
// 将N叉树的子树从右向左推入栈中,这样子树出栈的顺序是从左到右。
Collections.reverse(root.children);
for (Node n: root.children) {
stack.push(n);
}
}
return list;
}
}

3.树的中序遍历

  • 遍历过程为:
    • ①中序遍历其左子树
    • ②访问根结点
    • ③中序遍历其右子树
  • 对于二分搜索树来说,中序遍历使得元素从小到大排序。
  • 举例:
    • 下图的中序遍历结果为:1、2、3、4、5、6、7、8、9。

Alt text

①二叉树-递归

  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
// 递归函数定义: 中序遍历以root节点为根节点的二叉树
private void traversal(TreeNode root, List list) {
// 递归终止条件
if (root == null) {
return;
}
// 递归过程
// 中序遍历root节点的左子树
traversal(root.left, list);
// 处理当前节点
list.add(root.val);
// 中序遍历root节点的右子树
traversal(root.right, list);
}

public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
traversal(root, list);
return list;
}
}
  • C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 递归函数,returnSize、arr是指针,动态修改。
// 递归函数定义: 中序遍历以root节点为根节点的二叉树
void orderTraversal(struct TreeNode* root, int* returnSize, int* arr) {
// 递归终止条件
if (!root) {
return;
}
// 递归过程
// 中序遍历root节点的左子树
orderTraversal(root->left, returnSize, arr);
// 处理当前节点
arr[(*returnSize)++] = root->val;
// 中序遍历root节点的右子树
orderTraversal(root->right, returnSize, arr);
}

// 统计结点数
int makeSize(struct TreeNode* root) {
if (!root) {
return 0;
}
return makeSize(root->left) + makeSize(root->right) + 1;
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
int size = makeSize(root);
int* arr = (int*)malloc(sizeof(int) * size);
*returnSize = 0;
orderTraversal(root, returnSize, arr);
return arr;
}

②二叉树-迭代

  • 遇到一个节点,就把它压入栈中,并去遍历它的左子树。当左子树遍历结束后,弹出栈顶元素并访问它,再去中序遍历该节点的右子树。
  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
while (!stack.isEmpty() || root != null) {
// 遇到一个节点,就把它压入栈中,并去遍历它的左子树。
while (root != null) {
stack.push(root);
root = root.left;
}
// 当左子树遍历结束后,弹出栈顶元素并访问它。
if (!stack.isEmpty()) {
root = stack.pop();
list.add(root.val);
// 再去中序遍历该节点的右子树
root = root.right;
}
}
return list;
}
}
  • C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 统计结点数
int makeSize(struct TreeNode* root) {
if (!root)
return 0;

return makeSize(root->left) + makeSize(root->right) + 1;
}

typedef struct {
struct TreeNode** array;
int top;
} Stack;

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
int size = makeSize(root);
int* arr = (int*)malloc(sizeof(int) * size);
*returnSize = 0;
Stack* s = (Stack*)malloc(sizeof(Stack));
s->array = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * size);
s->top = -1;
while (s->top != -1 || root) {
// 遇到一个节点,就把它压入栈中,并去遍历它的左子树。
while (root) {
s->array[++s->top] = root;
root = root->left;
}
// 当左子树遍历结束后,弹出栈顶元素并访问它。
if (s->top != -1) {
root = s->array[s->top--];
arr[(*returnSize)++] = root->val;
// 再去中序遍历该节点的右子树
root = root->right;
}
}
return arr;
}

4.树的后序遍历

  • 遍历过程为:
    • ①后序遍历其左子树
    • ②后序遍历其右子树
    • ③访问根结点
  • 举例:
    • 下图的后序遍历结果为:1、2、3、4、5、6、7、8、9。

Alt text

①二叉树-递归

  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
// 递归函数定义: 后序遍历以root节点为根节点的二叉树
private void traversal(TreeNode root, List list) {
// 递归终止条件
if (root == null) {
return;
}
// 递归过程
// 后序遍历root节点的左子树
traversal(root.left, list);
// 后序遍历root节点的右子树
traversal(root.right, list);
// 处理当前节点
list.add(root.val);
}

public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
traversal(root, list);
return list;
}
}
  • C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 递归函数,returnSize、arr是指针,动态修改。
// 递归函数定义: 后序遍历以root节点为根节点的二叉树
void orderTraversal(struct TreeNode* root, int* returnSize, int* arr) {
// 递归终止条件
if (!root) {
return;
}
// 递归过程
// 后序遍历root节点的左子树
orderTraversal(root->left, returnSize, arr);
// 后序遍历root节点的右子树
orderTraversal(root->right, returnSize, arr);
// 处理当前节点
arr[(*returnSize)++] = root->val;
}

// 统计结点数
int makeSize(struct TreeNode* root) {
if (!root) {
return 0;
}
return makeSize(root->left) + makeSize(root->right) + 1;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
int size = makeSize(root);
int* arr = (int*)malloc(sizeof(int) * size);
*returnSize = 0;
orderTraversal(root, returnSize, arr);
return arr;
}

②二叉树-迭代

  • 后序遍历的顺序是:左右中
  • 先序遍历的顺序是:中左右
  • 所以我们可以先将先序遍历修改为:中右左,再将其遍历结果翻转存放,即可得到后序遍历的结果。
  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
// 先将先序遍历的中左右改为中右左,再将遍历结果翻转,即可得到后序遍历的左右中。
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
while (!stack.isEmpty() || root != null) {
// 遇到一个节点就访问它,然后把它压入栈中,并去遍历它的右子树。
while (root != null) {
list.add(root.val);
stack.push(root);
root = root.right;
}
// 当右子树遍历结束后,弹出栈顶元素。
if (!stack.isEmpty()) {
root = stack.pop();
// 再去"改写的先序"遍历该节点的左子树
root = root.left;
}
}
// 将遍历结果翻转
Collections.reverse(list);
return list;
}
}
  • C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 先将先序遍历的中左右改为中右左,再将遍历结果翻转,即可得到后序遍历的左右中。
// 统计结点数
int makeSize(struct TreeNode* root) {
if (!root)
return 0;

return makeSize(root->left) + makeSize(root->right) + 1;
}

typedef struct {
struct TreeNode** array;
int top;
} Stack;

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
int size = makeSize(root);
int* arr = (int*)malloc(sizeof(int) * size);
Stack* s = (Stack*)malloc(sizeof(Stack));
s->array = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * size);
s->top = -1;
*returnSize = size;
int row = *returnSize-1;
while (root || s->top != -1) {
// 遇到一个节点就访问它,然后把它压入栈中,并去遍历它的右子树。
while (root) {
// 反向存储遍历结果
arr[row--] = root->val;
s->array[++s->top] = root;
root = root->right;
}
// 当右子树遍历结束后,弹出栈顶元素。
if (s->top != -1) {
root = s->array[s->top--];
// 再去"改写的先序"遍历该节点的左子树
root = root->left;
}
}
return arr;
}

③N叉树-递归

  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
// 递归函数定义: 后序遍历以root节点为根节点的N叉树
private void traversal(Node root, List list) {
// 递归终止条件
if (root == null) {
return;
}
// 递归过程
// 后序遍历root节点的每个子树
for (Node node: root.children) {
traversal(node, list);
}
// 处理当前节点
list.add(root.val);
}
public List<Integer> postorder(Node root) {
List<Integer> list = new ArrayList<Integer>();
traversal(root, list);
return list;
}
}

④N叉树-迭代

  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
// 与二叉树的后序遍历——迭代法同理
public List<Integer> postorder(Node root) {
Stack<Node> stack = new Stack<>();
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
stack.push(root);
while (!stack.isEmpty()) {
root = stack.pop();
list.add(root.val);
// 将N叉树的子树从左向右推入栈中,这样子树出栈的顺序是从右到左。
for (Node n: root.children) {
stack.push(n);
}
}
// 将遍历结果翻转
Collections.reverse(list);
return list;
}
}

5.树的层序遍历

  • 从根节点开始,首先将根节点入队,然后开始执行循环:节点出队、访问该节点、其左右孩子入队。
  • 举例:
    • 下图的层序遍历结果为:5、2、8、1、4、6、9、3、7。

Alt text

注意:层序遍历的示例代码输出格式为下图所示格式。

Alt text

①二叉树-迭代

  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
// 将根节点入队
queue.add(root);
while (!queue.isEmpty()) {
// 使用count分层
int count = queue.size();
List<Integer> list = new ArrayList<>();
while (count-- > 0) {
// 节点出队
TreeNode node = queue.poll();
// 访问该节点
list.add(node.val);
// 其左右孩子入队
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
res.add(list);
}
return res;
}
}

②N叉树-迭代

  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<Node> queue = new LinkedList<>();
// 将根节点入队
queue.add(root);
while (!queue.isEmpty()) {
// 使用count分层
int count = queue.size();
List<Integer> list = new ArrayList<>();
while (count-- > 0) {
// 节点出队
Node node = queue.poll();
// 访问该节点
list.add(node.val);
// 其所有孩子从左到右依次入队
for (Node n: node.children) {
queue.add(n);
}
}
res.add(list);
}
return res;
}
}

6.总结

  • 前、中、后序遍历都属于 深度优先遍历
    • 即首先尝试走到最深,走不通之后再返回用回溯的方式将整棵树遍历结束。
    • 三种遍历实际访问节点的顺序相同,只是执行打印的位置不同。
    • 实现深度优先遍历:需要堆栈。
  • 层序遍历属于 广度优先遍历
    • 一层一层地遍历,关注广度,将每层的所有结点遍历完再去下一层。
    • 实现广度优先遍历:需要队列。

附录

0%