LeetCode hot 100—二叉树的中序遍历

题目

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

示例

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

分析

二叉树的中序遍历顺序是：先遍历左子树，然后访问根节点，最后遍历右子树。

递归法

递归是实现二叉树中序遍历最简单的方法，其基本思想是根据中序遍历的定义，递归地处理左子树、根节点和右子树。

时间复杂度：O( $n$ )， $n$ 为二叉树节点的个数

空间复杂度：O( $n$ )，递归调用栈的空间，最坏情况下二叉树退化为链表，递归深度为 $n$

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;inorder(root, result);return result;}
private:void inorder(TreeNode* node, vector<int>& result) {if (node == nullptr) {return;}// 递归遍历左子树inorder(node->left, result);// 访问根节点result.push_back(node->val);// 递归遍历右子树inorder(node->right, result);}
};

迭代法

迭代实现通常使用栈来模拟递归调用的过程。具体步骤如下：

从根节点开始，将左子树的节点依次压入栈中，直到左子树为空
弹出栈顶节点，访问该节点的值
处理该节点的右子树，重复步骤 1 和 2

时间复杂度：O( $n$ )， $n$ 为二叉树节点的个数

空间复杂度：O( $n$ )，递归调用栈的空间，最坏情况下二叉树退化为链表，递归深度为 $n$

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> nodeStack;TreeNode* current = root;while (current != nullptr || !nodeStack.empty()) {// 将左子树的节点依次压入栈中while (current != nullptr) {nodeStack.push(current);current = current->left;}// 弹出栈顶节点并访问current = nodeStack.top();nodeStack.pop();result.push_back(current->val);// 处理右子树current = current->right;}return result;}
};

知识充电

二叉树性质

若规定根节点的层数为 1，则一棵非空二叉树的第 i 层上最多有 $2^{i-1}$ 个节点

若规定根节点的层数为 1，则深度为 h 的二叉树的最大节点数是 $2^{h}-1$

对任何一棵二叉树，如果其叶节点个数为 $n_{0}$ ，度为 2 的非叶节点个数为 $n_{2}$ ，则有 $n_{0}=n_{2}+1$

常见操作

初始化

#include <iostream>
#include <vector>
#include <stack>// 二叉树节点定义
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

插入节点

// 插入节点（以二叉搜索树为例）
TreeNode* insertNode(TreeNode* root, int val) {if (root == nullptr) {return new TreeNode(val);}if (val < root->val) {root->left = insertNode(root->left, val);} else {root->right = insertNode(root->right, val);}return root;
}
int main() {TreeNode* root = nullptr;root = insertNode(root, 50);insertNode(root, 30);insertNode(root, 20);insertNode(root, 40);insertNode(root, 70);insertNode(root, 60);insertNode(root, 80);return 0;
}

查找节点

// 查找节点（以二叉搜索树为例）
TreeNode* searchNode(TreeNode* root, int val) {if (root == nullptr || root->val == val) {return root;}if (val < root->val) {return searchNode(root->left, val);} else {return searchNode(root->right, val);}
}
// 辅助函数：插入节点
TreeNode* insertNode(TreeNode* root, int val) {if (root == nullptr) {return new TreeNode(val);}if (val < root->val) {root->left = insertNode(root->left, val);} else {root->right = insertNode(root->right, val);}return root;
}
int main() {TreeNode* root = nullptr;root = insertNode(root, 50);insertNode(root, 30);insertNode(root, 20);insertNode(root, 40);insertNode(root, 70);insertNode(root, 60);insertNode(root, 80);TreeNode* found = searchNode(root, 40);if (found) {std::cout << "Found node with value: " << found->val << std::endl;} else {std::cout << "Node not found." << std::endl;}return 0;
}

删除节点

// 找到右子树中的最小节点
TreeNode* findMin(TreeNode* node) {while (node->left != nullptr) {node = node->left;}return node;
}
// 删除节点（以二叉搜索树为例）
TreeNode* deleteNode(TreeNode* root, int val) {if (root == nullptr) {return root;}if (val < root->val) {root->left = deleteNode(root->left, val);} else if (val > root->val) {root->right = deleteNode(root->right, val);} else {// 情况 1: 没有子节点或只有一个子节点if (root->left == nullptr) {TreeNode* temp = root->right;delete root;return temp;} else if (root->right == nullptr) {TreeNode* temp = root->left;delete root;return temp;}// 情况 2: 有两个子节点TreeNode* temp = findMin(root->right);root->val = temp->val;root->right = deleteNode(root->right, temp->val);}return root;
}
// 辅助函数：插入节点
TreeNode* insertNode(TreeNode* root, int val) {if (root == nullptr) {return new TreeNode(val);}if (val < root->val) {root->left = insertNode(root->left, val);} else {root->right = insertNode(root->right, val);}return root;
}
int main() {TreeNode* root = nullptr;root = insertNode(root, 50);insertNode(root, 30);insertNode(root, 20);insertNode(root, 40);insertNode(root, 70);insertNode(root, 60);insertNode(root, 80);root = deleteNode(root, 30);return 0;
}

前序遍历

// 前序遍历（递归）
std::vector<int> preorderTraversalRecursive(TreeNode* root) {std::vector<int> result;if (root == nullptr) return result;result.push_back(root->val);auto leftResult = preorderTraversalRecursive(root->left);result.insert(result.end(), leftResult.begin(), leftResult.end());auto rightResult = preorderTraversalRecursive(root->right);result.insert(result.end(), rightResult.begin(), rightResult.end());return result;
}
int main() {TreeNode* root = new TreeNode(1);root->right = new TreeNode(2);root->right->left = new TreeNode(3);std::vector<int> preorderRecursive = preorderTraversalRecursive(root);return 0;
}

中序遍历

// 中序遍历（递归）
std::vector<int> inorderTraversalRecursive(TreeNode* root) {std::vector<int> result;if (root == nullptr) return result;auto leftResult = inorderTraversalRecursive(root->left);result.insert(result.end(), leftResult.begin(), leftResult.end());result.push_back(root->val);auto rightResult = inorderTraversalRecursive(root->right);result.insert(result.end(), rightResult.begin(), rightResult.end());return result;
}
int main() {TreeNode* root = new TreeNode(1);root->right = new TreeNode(2);root->right->left = new TreeNode(3);std::vector<int> inorderRecursive = inorderTraversalRecursive(root);return 0;
}

后序遍历

// 后序遍历（递归）
std::vector<int> postorderTraversalRecursive(TreeNode* root) {std::vector<int> result;if (root == nullptr) return result;auto leftResult = postorderTraversalRecursive(root->left);result.insert(result.end(), leftResult.begin(), leftResult.end());auto rightResult = postorderTraversalRecursive(root->right);result.insert(result.end(), rightResult.begin(), rightResult.end());result.push_back(root->val);return result;
}
int main() {TreeNode* root = new TreeNode(1);root->right = new TreeNode(2);root->right->left = new TreeNode(3);std::vector<int> postorderRecursive = postorderTraversalRecursive(root);return 0;
}