面试经典算法22 - 二叉树的中序遍历
LeetCode.94
公众号：阿Q技术站
问题描述
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
思路
递归
- 如果根节点为空，返回空数组。
- 对根节点的左子树进行递归中序遍历，将结果存入结果数组。
- 将根节点的值存入结果数组。
- 对根节点的右子树进行递归中序遍历，将结果存入结果数组。
- 返回结果数组。
迭代
- 创建一个空数组
result用于存储遍历结果。 - 创建一个辅助栈
st用于存储遍历过程中的节点。 - 如果根节点为空，直接返回空数组。
- 从根节点开始，依次将左子节点入栈，直到左子节点为空。
- 弹出栈顶节点，将节点值加入结果数组，并将当前节点指向右子节点。
- 重复步骤 2 和步骤 3，直到栈为空且当前节点为空。
图解
这里还是给大家使用迭代法做一个图解。
- 先将头结点插入栈中。
- 左节点不为空时，将左节点插入栈中，直至左节点遍历完。
- 弹出栈顶元素，并添加至结果集。
- 将根节点的右子节点添加进栈中。
- 将右子节点的左子节点添加进栈中
- 当前根节点（右子节点）的左子节点遍历完成，取出栈顶元素，并添加进结果集。
- 继续将右子节点添加进栈中，直至遍历完。
- 弹出栈顶元素，并添加进结果集。
参考代码
C++
递归
#include <iostream>
#include <vector>
using namespace std;
// 二叉树节点的定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 递归中序遍历
void inorderTraversal(TreeNode* root, vector<int>& result) {
if (root == nullptr) {
return; // 如果节点为空，直接返回
}
inorderTraversal(root->left, result); // 递归遍历左子树
result.push_back(root->val); // 将根节点的值加入结果数组
inorderTraversal(root->right, result); // 递归遍历右子树
}
// 创建二叉树
TreeNode* createTree(vector<int>& nodes, int index) {
if (index >= nodes.size() || nodes[index] == -1) {
return nullptr; // 如果节点为空，则返回nullptr
}
TreeNode* root = new TreeNode(nodes[index]); // 创建当前节点
root->left = createTree(nodes, 2 * index + 1); // 创建左子树
root->right = createTree(nodes, 2 * index + 2); // 创建右子树
return root; // 返回当前节点
}
// 销毁二叉树
void destroyTree(TreeNode* root) {
if (!root) return; // 如果根节点为空，直接返回
destroyTree(root->left); // 递归销毁左子树
destroyTree(root->right); // 递归销毁右子树
delete root; // 删除当前节点
}
int main() {
vector<int> nodes = {1, 2, 3, -1, -1, 4, 5}; // 定义二叉树的先序遍历序列
TreeNode* root = createTree(nodes, 0); // 创建二叉树
vector<int> result; // 存储遍历结果的数组
inorderTraversal(root, result); // 进行递归中序遍历
for (int val : result) { // 输出遍历结果
cout << val << " ";
}
cout << endl;
destroyTree(root); // 销毁二叉树
return 0;
}
迭代
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// 二叉树节点的定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 中序遍历
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result; // 存储遍历结果的数组
stack<TreeNode*> st; // 辅助栈，用于存储遍历过程中的节点
while (root != nullptr || !st.empty()) {
while (root != nullptr) { // 将左子节点入栈直到为空
st.push(root);
root = root->left;
}
root = st.top(); // 弹出栈顶节点
st.pop();
result.push_back(root->val); // 将节点值加入结果数组
root = root->right; // 处理右子节点
}
return result; // 返回中序遍历结果数组
}
// 创建二叉树
TreeNode* createTree(vector<int>& nodes, int index) {
if (index >= nodes.size() || nodes[index] == -1) {
return nullptr; // 如果节点为空，则返回nullptr
}
TreeNode* root = new TreeNode(nodes[index]); // 创建当前节点
root->left = createTree(nodes, 2 * index + 1); // 创建左子树
root->right = createTree(nodes, 2 * index + 2); // 创建右子树
return root; // 返回当前节点
}
// 销毁二叉树
void destroyTree(TreeNode* root) {
if (!root) return; // 如果根节点为空，直接返回
destroyTree(root->left); // 递归销毁左子树
destroyTree(root->right); // 递归销毁右子树
delete root; // 删除当前节点
}
int main() {
vector<int> nodes = {1, 2, 3, -1, -1, 4, 5}; // 定义二叉树的先序遍历序列
TreeNode* root = createTree(nodes, 0); // 创建二叉树
vector<int> result = inorderTraversal(root); // 进行中序遍历
for (int val : result) { // 输出遍历结果
cout << val << " ";
}
cout << endl;
destroyTree(root); // 销毁二叉树
return 0;
}
Java
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
/**
* 中序遍历二叉树
* @param root 二叉树的根节点
* @return 中序遍历结果
*/
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = 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(); // 弹出栈顶节点
result.add(curr.val); // 将节点值加入结果列表
curr = curr.right; // 处理右子节点
}
return result; // 返回中序遍历结果列表
}
public static void main(String[] args) {
int[] nodes = {1, 2, 3, -1, -1, 4, 5}; // 二叉树的先序遍历序列
TreeNode root = createTree(nodes, 0); // 创建二叉树
Solution solution = new Solution();
List<Integer> result = solution.inorderTraversal(root); // 进行中序遍历
for (int val : result) { // 输出遍历结果
System.out.print(val + " ");
}
System.out.println();
}
/**
* 根据先序遍历序列创建二叉树
* @param nodes 二叉树的先序遍历序列
* @param index 当前节点在序列中的索引
* @return 创建的二叉树的根节点
*/
private static TreeNode createTree(int[] nodes, int index) {
if (index >= nodes.length || nodes[index] == -1) {
return null; // 如果节点为空，则返回null
}
TreeNode root = new TreeNode(nodes[index]); // 创建当前节点
root.left = createTree(nodes, 2 * index + 1); // 创建左子树
root.right = createTree(nodes, 2 * index + 2); // 创建右子树
return root; // 返回当前节点
}
}
Python
# 二叉树节点的定义
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def inorderTraversal(root):
result = [] # 存储遍历结果的数组
stack = [] # 辅助栈，用于存储遍历过程中的节点
while root or stack:
while root: # 将左子节点入栈直到为空
stack.append(root)
root = root.left
root = stack.pop() # 弹出栈顶节点
result.append(root.val) # 将节点值加入结果数组
root = root.right # 处理右子节点
return result # 返回中序遍历结果数组
def createTree(nodes, index):
if index >= len(nodes) or nodes[index] == -1:
return None # 如果节点为空，则返回None
root = TreeNode(nodes[index]) # 创建当前节点
root.left = createTree(nodes, 2 * index + 1) # 创建左子树
root.right = createTree(nodes, 2 * index + 2) # 创建右子树
return root # 返回当前节点
def destroyTree(root):
if not root:
return # 如果根节点为空，直接返回
destroyTree(root.left) # 递归销毁左子树
destroyTree(root.right) # 递归销毁右子树
del root # 删除当前节点
# 测试
nodes = [1, 2, 3, -1, -1, 4, 5] # 定义二叉树的先序遍历序列
root = createTree(nodes, 0) # 创建二叉树
result = inorderTraversal(root) # 进行中序遍历
print(result) # 输出遍历结果
destroyTree(root) # 销毁二叉树
