algorithm - 我们可以使用 Morris 遍历进行后序吗？

Question

我访问了很多网站，但找不到任何用于 Morris postOrder 遍历的算法。我知道我们可以对 preOrder 和 inOrder 使用 Morris 算法。如果有人向我指出 postOrder Morris 算法(如果存在)，那将会有很大帮助。

Answer 1

一种更简单的方法是执行与预序莫里斯遍历对称相反的操作，并以相反的顺序打印节点。

    TreeNode* node = root;
    stack<int> s;
    while(node) {
        if(!node->right) {
            s.push(node->val);
            node = node->left;
        }
        else {
            TreeNode* prev = node->right;

            while(prev->left && prev->left != node)
                prev = prev->left;

            if(!prev->left) {
                prev->left = node;
                s.push(node->val);
                node = node->right;
            }
            else {  
                node = node->left;
                prev->left = NULL;
            }
        }
    }

    while(!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }

    cout << endl;