请给我列举出两个用C++语言实现二叉树的递归与非递归遍历时可能遇到的问题以及解决方案并且给出代码举例
时间: 2023-12-10 11:41:13 浏览: 34
问题1:递归遍历时可能会引起栈溢出
解决方案:可以使用非递归的方式遍历二叉树,或者使用尾递归优化来避免栈溢出。
代码示例:
```c++
// 尾递归优化的先序遍历
void preOrder(TreeNode* root) {
if (!root) return;
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
void preOrderTailRecursion(TreeNode* root) {
while (root) {
cout << root->val << " ";
if (root->left) root = root->left;
else root = root->right;
}
}
```
问题2:非递归遍历时可能会遇到空指针或者重复访问节点
解决方案:在遍历时需要判断当前节点是否为空指针,以及使用一个辅助数据结构(如栈)来记录已经访问过的节点。
代码示例:
```c++
// 非递归的中序遍历
void inOrder(TreeNode* root) {
stack<TreeNode*> s;
while (root || !s.empty()) {
if (root) {
s.push(root);
root = root->left;
} else {
root = s.top(); s.pop();
cout << root->val << " ";
root = root->right;
}
}
}
```