二叉树的遍历，递归和非递归-蒲公英云

二叉树的遍历，递归和非递归

向右看齐 2024-04-17 05:44 168阅读 0赞

1，中序遍历

非递归版本，借助一个辅助

vector<int> ans;
vector<int> inorderTraversal(TreeNode* root) {
    TreeNode *node = root;
    stack<TreeNode *> mstack;
    while(node != NULL || !mstack.empty())
    {
    while(node != NULL)
    {
        mstack.push(node); // 注意这里入栈不能写指针，写结点
        node = node->left;
    }
        ans.push_back(mstack.top()->val); // 注意这里是 .
        node = mstack.top()->right;
        mstack.pop(); 
    }
    return ans;
}

递归版本，简洁

vector<int> ans;
vector<int> inorderTraversal(TreeNode* root) 
{
    if(root != NULL)
    {
        inorderTraversal(root->left);
        ans.push_back(root->val);
        inorderTraversal(root->right);
    }
  return ans;
}

2，二叉树的后续遍历

非递归版本，后续遍历稍微麻烦点，通过设置一个 “前一个节点”变量，来记录下一次应该访问的结点

vector<int> ans;
vector<int> postorderTraversal(TreeNode* root) 
{
    if(root == NULL) 
        return ans;
    stack<TreeNode*> mstack;
    TreeNode* pre = NULL; //前一个节点
    while(!mstack.empty()|| root != NULL)
    {
        if(root != NULL)
        {
            mstack.push(root);
            root = root->left;
        }
        else
        {
            root=mstack.top();
            if(root->right == NULL || root->right == pre)
            {
                //如果右子树不存在，则接下来该访问根节点。
                mstack.pop();
                ans.push_back(root->val);
                pre = root;
                root = NULL;
            }
            else
            {
                //否则柚子树存在，就先访问右子树
                pre = NULL;
                root = root->right;
            }
        }
    }
    return ans;
}

递归版本，简洁

vector<int> ans;
vector<int> postorderTraversal(TreeNode* root) {
    if(root != NULL)
    {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        ans.push_back(root->val);
    }
    return ans;
}