本文共 1775 字，大约阅读时间需要 5 分钟。

话不多说，前两种直接上代码：

递归方法：

void preOrder(TreeNode* root){    if(root != NULL){        preOrder(root->left);        cout << root->val << " ";        preOrder(root->right);    }}

循环方法：

void preOrder(TreeNode* root){    if(root == NULL) return;    stack
   
     S;    TreeNode* node = root;    while(node!=NULL || !S.empty()){    	if(node != NULL)}{    	     // cout << node->val << " ";  先序遍历：在push时访问结点值 			 S.push(node);        	  node = node->left;    	}    	else{            cout << node->val << " ";   // 中序遍历：在弹出栈顶指针时访问            node = S.top()->right;            S.pop();    	}      }}
   

上述两种方法，时间复杂度为O(nlgn),空间复杂度为O(n)

优化空间复杂度为O(1)的方法：利用线索二叉树的概念

如果不能用栈空间，一个明显的问题是：如何返回到父节点。

线索二叉树利用叶子节点中的左右空指针指向某种顺序遍历下的前驱节点或后继节点就可以。

步骤如下：

1. 如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。

2. 如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点。 a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点。当前节点(Cur)更新为当前节点的左孩子

3. 重复以上1、2直到当前节点（Cur）为空。

画图示意：

图片和步骤来源：

具体代码如下：

void recoverTree(TreeNode *root)///这里是采用O(1)的算法    {        if(root==NULL)            return;        TreeNode* pre=NULL;        TreeNode* cur=root;        while(cur)        {            if(cur->left==NULL)            {                cout<
   
    val;                cur=cur->right;            }            else            {                pre=cur->left;                while(pre->right!=NULL&&pre->right!=cur)                    pre=pre->right;                if(pre->right==NULL)                {                    pre->right=cur;                    cur=cur->left;                }                else                {                    pre->right=NULL;                    cout<
    
     val;                    cur=cur->right;                }            }        }    }
    
   

转载地址：https://blog.csdn.net/weixin_40599276/article/details/100120601 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！