tree traversal (树的遍历) - 中序遍历 (inorder traversal) - 二叉树的中序遍历

作者：小丑西瓜9 | 2024-05-27 18:05:55

踩

inorder traversal

tree traversal (树的遍历) - 中序遍历 (inorder traversal) - 二叉树的中序遍历

树的遍历是当且仅当访问树中每个节点一次的过程。遍历可以解释为把所有的节点放在一条线上，或者将树线性化。

1. tree traversal (树的遍历)

1.1 深度优先搜索 (depth-first search，DFS)

我们采用深度作为优先级，从根节点开始一直到达某个确定的叶子节点，然后再返回根节点到达另一个分支。深度优先搜索策略可以根据根节点、左孩子树和右孩子树的相对顺序被细分为前序遍历、中序遍历和后序遍历。

前序遍历 (preorder traversal) - 中序遍历 (inorder traversal) - 后序遍历 (postorder traversal)

1.2 广度优先搜索 - 宽度优先搜索 - 横向优先搜索 (breadth-first search，BFS)

我们按照高度顺序一层一层的访问整棵树，高层次的节点将会比低层次的节点先被访问到。

下图中的节点依照不同的策略遍历，访问的顺序均为 1, 2, 3, 4, 5。宽度优先搜索划分层次为 [[1], [2, 3], [4, 5]]。
在这里插入图片描述

递归实现的效率一般比对应的非递归实现低。如果在函数中使用了两个递归调用，效率低下的问题就会变得更为严重。

2. 二叉树的中序遍历

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

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,3,2]
1
2
3
4
5
6
7
8

int* inorderTraversal(struct TreeNode* root, int* returnSize)
1

输入参数 root 为 NULL 时，如果 return NULL，*returnSize 必须设置为 0。

2.1 迭代实现 - 数组模拟栈 (stack) 的操作

//============================================================================
// Name        : inorder traversal
// Author      : Yongqiang Cheng
// Version     : Feb 22, 2020
// Copyright   : Copyright (c) 2020 Yongqiang Cheng
// Description : Hello World in C++, Ansi-style
//============================================================================

/*
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
	int front = 0, idx = 0;
	struct TreeNode* STACK_DATA[512] =
	{ NULL };
	int *ret = (int *) malloc(512 * sizeof(int));
	struct TreeNode* pnode = NULL;

	*returnSize = 0;
	if (NULL == root)
	{
		return NULL;
	}

	if (NULL == ret)
	{
		return NULL;
	}

	front = -1;
	STACK_DATA[++front] = root;

	while (front >= 0)
	{
		while (NULL != STACK_DATA[front])
		{
			pnode = STACK_DATA[front]->left;
			STACK_DATA[++front] = pnode;
		}

		--front;

		if (front >= 0)
		{
			pnode = STACK_DATA[front];
			ret[idx] = pnode->val;
			idx++;
			STACK_DATA[front] = pnode->right;
		}
	}

	*returnSize = idx;

	return ret;
}

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66