请用morris遍历遍历一颗完全平衡二叉树
时间: 2023-04-01 11:03:52 浏览: 79
可以使用 Morris 遍历算法来遍历一颗完全平衡二叉树。该算法的时间复杂度为 O(n),空间复杂度为 O(1)。具体实现方法可以参考以下代码:
```
void morrisTraversal(TreeNode* root) {
TreeNode* cur = root;
while (cur != nullptr) {
if (cur->left == nullptr) {
// 如果当前节点没有左子树,则直接访问该节点
cout << cur->val << " ";
cur = cur->right;
} else {
// 如果当前节点有左子树,则找到左子树的最右节点
TreeNode* pre = cur->left;
while (pre->right != nullptr && pre->right != cur) {
pre = pre->right;
}
if (pre->right == nullptr) {
// 如果最右节点的右子树为空,则将其指向当前节点
pre->right = cur;
cur = cur->left;
} else {
// 如果最右节点的右子树指向当前节点,则说明左子树已经遍历完毕,可以访问当前节点
pre->right = nullptr;
cout << cur->val << " ";
cur = cur->right;
}
}
}
}
```