《二叉树遍历原理与OJ算法解题策略深度解析》
二叉树作为基础数据结构，其遍历操作与算法解题有着紧密联系。本文将系统探讨二叉树遍历的核心机制，并结合OJ（在线评测）题目分析暴力解法中的优化策略。
**二叉树基础结构**
```cpp
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
```
**递归遍历的经典实现**
1. **前序遍历**
```cpp
void preorderTraversal(TreeNode* root, vector<int>& result) {
if (!root) return;
result.push_back(root->val); // 访问根节点
preorderTraversal(root->left, result); // 遍历左子树
preorderTraversal(root->right, result); // 遍历右子树
}
```
2. **中序遍历**
```cpp
void inorderTraversal(TreeNode* root, vector<int>& result) {
if (!root) return;
inorderTraversal(root->left, result); // 遍历左子树
result.push_back(root->val); // 访问根节点
inorderTraversal(root->right, result); // 遍历右子树
}
```
3. **后序遍历**
```cpp
void postorderTraversal(TreeNode* root, vector<int>& result) {
if (!root) return;
postorderTraversal(root->left, result); // 遍历左子树
postorderTraversal(root->right, result); // 遍历右子树
result.push_back(root->val); // 访问根节点
}
```
**迭代遍历的实用实现**
1. **迭代前序遍历**
```cpp
vector<int> preorderIterative(TreeNode* root) {
vector<int> result;
if (!root) return result;
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty()) {
TreeNode* node = stk.top();
stk.pop();
result.push_back(node->val);
// 先右后左，保证左子树先被访问
if (node->right) stk.push(node->right);
if (node->left) stk.push(node->left);
}
return result;
}
```
2. **迭代中序遍历**
```cpp
vector<int> inorderIterative(TreeNode* root) {
vector<int> result;
stack<TreeNode*> stk;
TreeNode* curr = root;
while (curr || !stk.empty()) {
// 一直向左走到尽头
while (curr) {
stk.push(curr);
curr = curr->left;
}
curr = stk.top();
stk.pop();
result.push_back(curr->val);
// 转向右子树
curr = curr->right;
}
return result;
}
```
3. **迭代后序遍历**
```cpp
vector<int> postorderIterative(TreeNode* root) {
vector<int> result;
if (!root) return result;
stack<TreeNode*> stk;
TreeNode* lastVisited = nullptr;
TreeNode* curr = root;
while (curr || !stk.empty()) {
if (curr) {
stk.push(curr);
curr = curr->left;
} else {
TreeNode* peekNode = stk.top();
// 如果右子树存在且未被访问
if (peekNode->right && lastVisited != peekNode->right) {
curr = peekNode->right;
} else {
result.push_back(peekNode->val);
lastVisited = peekNode;
stk.pop();
}
}
}
return result;
}
```
**层次遍历及其变体**
```cpp
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if (!root) return result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
vector<int> levelNodes;
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
levelNodes.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
result.push_back(levelNodes);
}
return result;
}
// Zigzag层次遍历
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> result;
if (!root) return result;
queue<TreeNode*> q;
q.push(root);
bool leftToRight = true;
while (!q.empty()) {
int levelSize = q.size();
vector<int> levelNodes(levelSize);
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
// 根据方向决定插入位置
int index = leftToRight ? i : levelSize - 1 - i;
levelNodes[index] = node->val;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
result.push_back(levelNodes);
leftToRight = !leftToRight;
}
return result;
}
```
**OJ题目暴力解法分析**
1. **二叉树最大深度**
```cpp
// 暴力递归解法
int maxDepth(TreeNode* root) {
if (!root) return 0;
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return max(leftDepth, rightDepth) + 1;
}
// 迭代BFS解法
int maxDepthBFS(TreeNode* root) {
if (!root) return 0;
queue<TreeNode*> q;
q.push(root);
int depth = 0;
while (!q.empty()) {
depth++;
int levelSize = q.size();
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return depth;
}
```
2. **对称二叉树检查**
```cpp
// 暴力递归解法
bool isSymmetric(TreeNode* root) {
if (!root) return true;
return isMirror(root->left, root->right);
}
bool isMirror(TreeNode* left, TreeNode* right) {
if (!left && !right) return true;
<"e7.j9k5.org.cn"><"u9.j9k5.org.cn"><"b2.j9k5.org.cn">
if (!left || !right) return false;
if (left->val != right->val) return false;
return isMirror(left->left, right->right) &&
isMirror(left->right, right->left);
}
// 迭代解法
bool isSymmetricIterative(TreeNode* root) {
if (!root) return true;
queue<pair<TreeNode*, TreeNode*>> q;
q.push({root->left, root->right});
while (!q.empty()) {
auto [left, right] = q.front();
q.pop();
if (!left && !right) continue;
if (!left || !right) return false;
if (left->val != right->val) return false;
q.push({left->left, right->right});
q.push({left->right, right->left});
}
return true;
}
```
**路径相关问题的暴力搜索**
```cpp
// 二叉树所有路径
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
if (!root) return result;
vector<int> path;
dfsPaths(root, path, result);
return result;
}
void dfsPaths(TreeNode* node, vector<int>& path, vector<string>& result) {
path.push_back(node->val);
// 叶子节点，记录路径
if (!node->left && !node->right) {
string pathStr;
for (int i = 0; i < path.size(); i++) {
pathStr += to_string(path[i]);
if (i < path.size() - 1) pathStr += "->";
}
result.push_back(pathStr);
}
if (node->left) dfsPaths(node->left, path, result);
if (node->right) dfsPaths(node->right, path, result);
path.pop_back(); // 回溯
}
// 路径总和问题
bool hasPathSum(TreeNode* root, int targetSum) {
if (!root) return false;
// 叶子节点检查
if (!root->left && !root->right) {
return root->val == targetSum;
}
int newSum = targetSum - root->val;
return hasPathSum(root->left, newSum) ||
hasPathSum(root->right, newSum);
}
```
**子树与子结构问题**
```cpp
// 判断子树
bool isSubtree(TreeNode* s, TreeNode* t) {
if (!s) return false;
// 检查当前节点开始的子树
if (isSameTree(s, t)) return true;
// 递归检查左右子树
return isSubtree(s->left, t) || isSubtree(s->right, t);
}
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) return true;
if (!p || !q) return false;
if (p->val != q->val) return false;
return isSameTree(p->left, q->left) &&
isSameTree(p->right, q->right);
}
// 优化版本 - 序列化+哈希
class SubtreeChecker {
private:
unordered_map<string, bool> memo;
public:
bool isSubtreeEfficient(TreeNode* s, TreeNode* t) {
string tSerial = serialize(t);
checkTree(s, tSerial);
return memo[tSerial];
}
string serialize(TreeNode* root) {
if (!root) return "#";
string left = serialize(root->left);
string right = serialize(root->right);
return to_string(root->val) + "," + left + "," + right;
}
string checkTree(TreeNode* node, const string& target) {
if (!node) return "#";
string left = checkTree(node->left, target);
string right = checkTree(node->right, target);
string current = to_string(node->val) + "," + left + "," + right;
if (current == target) {
memo[target] = true;
}
return current;
}
};
```
**最近公共祖先问题**
```cpp
// 暴力搜索解法
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left && right) return root; // p和q在左右子树
if (left) return left; // 都在左子树
return right; // 都在右子树
}
// 带路径记录的优化版本
class LCASolution {
public:
<"x5.j9k5.org.cn"><"r1.j9k5.org.cn"><"k8.j9k5.org.cn"><"p0.j9k5.org.cn">
TreeNode* lowestCommonAncestorWithPath(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> pathP, pathQ;
// 查找路径
findPath(root, p, pathP);
findPath(root, q, pathQ);
// 比较路径
TreeNode* lca = nullptr;
int minLength = min(pathP.size(), pathQ.size());
for (int i = 0; i < minLength; i++) {
if (pathP[i] == pathQ[i]) {
lca = pathP[i];
} else {
break;
}
}
return lca;
}
private:
bool findPath(TreeNode* root, TreeNode* target, vector<TreeNode*>& path) {
if (!root) return false;
path.push_back(root);
if (root == target) return true;
if (findPath(root->left, target, path) ||
findPath(root->right, target, path)) {
return true;
}
path.pop_back();
return false;
}
};
```
**二叉搜索树相关问题**
```cpp
// 验证二叉搜索树
bool isValidBST(TreeNode* root) {
return validateBST(root, nullptr, nullptr);
}
bool validateBST(TreeNode* node, TreeNode* minNode, TreeNode* maxNode) {
if (!node) return true;
if ((minNode && node->val <= minNode->val) ||
(maxNode && node->val >= maxNode->val)) {
return false;
}
return validateBST(node->left, minNode, node) &&
validateBST(node->right, node, maxNode);
}
// BST中第K小的元素
int kthSmallest(TreeNode* root, int k) {
vector<int> inorder;
inorderTraversal(root, inorder);
return inorder[k - 1];
}
// 优化版本 - 提前终止的中序遍历
class KthSmallestFinder {
private:
int count = 0;
int result = 0;
public:
int kthSmallestOptimized(TreeNode* root, int k) {
inorderSearch(root, k);
return result;
}
void inorderSearch(TreeNode* node, int k) {
if (!node) return;
inorderSearch(node->left, k);
count++;
if (count == k) {
result = node->val;
return;
}
inorderSearch(node->right, k);
}
};
```
**重构二叉树问题**
```cpp
// 前序+中序重建二叉树
TreeNode* buildTreeFromPreInorder(vector<int>& preorder, vector<int>& inorder) {
unordered_map<int, int> inorderMap;
for (int i = 0; i < inorder.size(); i++) {
inorderMap[inorder[i]] = i;
}
return buildHelper(preorder, 0, preorder.size() - 1,
inorder, 0, inorder.size() - 1, inorderMap);
}
TreeNode* buildHelper(vector<int>& preorder, int preStart, int preEnd,
vector<int>& inorder, int inStart, int inEnd,
unordered_map<int, int>& inorderMap) {
if (preStart > preEnd || inStart > inEnd) return nullptr;
int rootVal = preorder[preStart];
TreeNode* root = new TreeNode(rootVal);
int rootIndex = inorderMap[rootVal];
int leftSize = rootIndex - inStart;
root->left = buildHelper(preorder, preStart + 1, preStart + leftSize,
inorder, inStart, rootIndex - 1, inorderMap);
root->right = buildHelper(preorder, preStart + leftSize + 1, preEnd,
inorder, rootIndex + 1, inEnd, inorderMap);
return root;
}
// 后序+中序重建二叉树
TreeNode* buildTreeFromPostInorder(vector<int>& postorder, vector<int>& inorder) {
unordered_map<int, int> inorderMap;
for (int i = 0; i < inorder.size(); i++) {
inorderMap[inorder[i]] = i;
}
return buildHelperPost(postorder, 0, postorder.size() - 1,
inorder, 0, inorder.size() - 1, inorderMap);
}
TreeNode* buildHelperPost(vector<int>& postorder, int postStart, int postEnd,
vector<int>& inorder, int inStart, int inEnd,
unordered_map<int, int>& inorderMap) {
if (postStart > postEnd || inStart > inEnd) return nullptr;
int rootVal = postorder[postEnd];
TreeNode* root = new TreeNode(rootVal);
int rootIndex = inorderMap[rootVal];
int leftSize = rootIndex - inStart;
root->left = buildHelperPost(postorder, postStart, postStart + leftSize - 1,
inorder, inStart, rootIndex - 1, inorderMap);
root->right = buildHelperPost(postorder, postStart + leftSize, postEnd - 1,
inorder, rootIndex + 1, inEnd, inorderMap);
return root;
}
```
**暴力美学的优化策略**
1. **记忆化搜索**
```cpp
class BalancedTreeChecker {
private:
unordered_map<TreeNode*, bool> balancedMemo;
unordered_map<TreeNode*, int> heightMemo;
public:
bool isBalanced(TreeNode* root) {
if (!root) return true;
// 记忆化检查
if (balancedMemo.find(root) != balancedMemo.end()) {
return balancedMemo[root];
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
bool balanced = abs(leftHeight - rightHeight) <= 1 &&
isBalanced(root->left) &&
isBalanced(root->right);
balancedMemo[root] = balanced;
return balanced;
}
int getHeight(TreeNode* node) {
if (!node) return 0;
// 记忆化高度计算
if (heightMemo.find(node) != heightMemo.end()) {
return heightMemo[node];
}
int height = 1 + max(getHeight(node->left), getHeight(node->right));
heightMemo[node] = height;
return height;
}
};
```
2. **剪枝优化**
```cpp
// 路径总和III - 暴力搜索优化
class PathSumIII {
public:
int pathSum(TreeNode* root, int targetSum) {
if (!root) return 0;
// 从当前节点开始的路径
int countFromRoot = countPaths(root, targetSum);
// 从左子树和右子树开始的路径
int leftCount = pathSum(root->left, targetSum);
int rightCount = pathSum(root->right, targetSum);
return countFromRoot + leftCount + rightCount;
}
private:
int countPaths(TreeNode* node, long long remaining) {
if (!node) return 0;
int count = 0;
// 如果当前节点值等于剩余值，找到一条路径
if (node->val == remaining) {
count++;
}
// 继续搜索左右子树
count += countPaths(node->left, remaining - node->val);
count += countPaths(node->right, remaining - node->val);
return count;
}
};
```
**总结与实战建议**
二叉树遍历与OJ解题的核心要点：
1. **递归与迭代的平衡**
- 递归代码简洁但可能栈溢出
- 迭代效率稳定但实现复杂
- 根据问题规模选择合适方法
2. **暴力解法的优化路径**
- 添加记忆化避免重复计算
- 实施剪枝减少无效搜索
- 利用问题特性简化搜索空间
3. **算法选择的决策树**
```
问题类型 → 解决方案
├── 遍历问题 → BFS/DFS
├── 路径问题 → DFS + 回溯
├── 祖先问题 → 递归搜索
├── 验证问题 → 特性检查
└── 重构问题 → 分治策略
```
4. **实际编码技巧**
- 使用辅助数据结构记录状态
- 注意边界条件和空指针
- 考虑大规模数据的性能
二叉树问题的暴力解法虽然直接，但通过合理的优化和剪枝，能够在OJ环境中达到理想性能。理解遍历原理并灵活运用搜索策略，是解决复杂树形结构问题的关键能力。
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/19545/viewspace-3109380/ ，如需转载，请注明出处，否则将追究法律责任。
