二叉树后序非递归遍历

2023-12-30 22:03:34

这里我们知道二叉树的后序遍历,是先遍历左子树,然后右子树,最后是根结点。

因此我们要先

1.找到二叉树最左边的结点,然后判断其右子树是否为空.

2.若右子树不为空,则在右子树上从步骤1开始重复执行知道右子树为空。若右子树为空,则访问该结点,然后找到结点的父亲节点,然后重复从步骤2的操作。

3.重复步骤1,2。直到全部结点都遍历完。

这里我通过图来具体解释。

这里我们找到树的最左节点D,判断D的右子树为空,则访问D结点(即打印D),然后找到D的父亲B结点。判断B的右子树不为空。则找到B结点的右子树的最左节点E。E的右子树为空。访问E结点,B结点的左右子树都访问完,访问B结点。

然后遍历A结点的右子树与左子树方法一样。

这里由于我们是非递归的方法,那么我们要如何让记录父结点(B,A)呢?

这里我们使用栈,记录在查找树最左结点的过程中经过的所有结点。

?

每访问过一个结点就将结点出栈。直到栈空为止。

这里我们以leetcode第145题为例。

这里我们直接上代码:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        TreeNode* cur=root;
        stack<TreeNode*>st;
        vector<int>s;
        while(cur||!st.empty())//特殊情况空树
        {
            while(cur)//将查找最左节点所经过的结点都放到栈里
            {
                st.push(cur);
                cur=cur->left;
            }
            TreeNode* temp=st.top()
            if(temp->right==nullptr)//最左节点的右子树为空
            {
                s.push_back(temp->val);
                st.pop();
            }
            else
            {
                cur=temp->right;//最左节点的右子树不为空,重复循环找右子树的最左节点
            }
        }
        return s;
    }
};

这里但我们提交后会发现时间超时。

这里我们可以通过一个上图的例子一个一个的带入,查找错误。这里我们会发现:

当程序会卡在B结点处。因为当第二次到B结点时,都会判断其右节点不为空。导致重复入栈。

因此我们需要想办法区分B的右子树是否入过栈。

这里我们可以通过记录上一个出栈的变量来解决(第二次到B结点时,上一个结点一定是B的右节点E)

完善代码:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        TreeNode* cur=root;
        TreeNode* prev=nullptr;
        stack<TreeNode*>st;
        vector<int>s;
        while(cur||!st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur=cur->left;
            }
            TreeNode* temp=st.top();
            if(temp->right==nullptr||prev==temp->right)
            {
                st.pop();
                s.push_back(temp->val);
                prev=temp;
            }
            else
            {
                cur=temp->right;
            }
        }
        return s;
    }
};

文章来源:https://blog.csdn.net/qq_63440853/article/details/135308751
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。