二叉树非递归后序遍历C++

方法一： 我们可以发现二叉树的后序遍历=镜像二叉树的先序遍历的反向输出。于是需要： 1.得到镜像二叉树 2.非递归的先序遍历镜像二叉树 3.将节点的访问结果存储在栈中，利用先入后出的特点将输出结果的顺序反向

class Tree { public: TreeNode* invertTree(TreeNode* root) { if (root == nullptr) return nullptr; TreeNode* left = invertTree(root->left); TreeNode* right = invertTree(root->right); root->left = right; root->right = left; return root; } }; class Solution { public: vector<int> postorderTraversal(TreeNode* root) { Tree operate; vector<int> ans; TreeNode* invertRoot = operate.invertTree(root); TreeNode* T = invertRoot; stack<TreeNode*> s; stack<int> sout; while (T != nullptr || !s.empty()) { while (T != nullptr) { //cout << T->val << " "; sout.push(T->val); s.push(T); T = T->left; } T = s.top(); s.pop(); T = T->right; } while (!sout.empty()) { ans.push_back(sout.top()); sout.pop(); } return ans; } };

方法二：设置两个节点指针，一个指向当前节点，一个指向上一个被访问的右子树。

void postorderNonRecur2(TreeNode* root) { TreeNode* T = root; TreeNode* tempRight=nullptr; stack<TreeNode*> s; while (T != nullptr || !s.empty()) { while (T != nullptr) { s.push(T); T = T->left; } T = s.top(); if (T->right == nullptr || T->right == tempRight)//如果右子树不存在或者右子树已被访问 { cout << T->val << " "; tempRight = T; s.pop(); T = nullptr; } else { T = T->right; s.push(T); T = T->left; } } }

这是由于后序遍历中，在当前根节点之前被访问的右子树一定是该根节点的右子树，所以可以再用一个指针存储右子树，以此来判断根节点的右子树是否被访问过。是，则可以访问该根节点；否则，右子树也入栈，然后继续转向左子树。