The simplest Iterative & Morris solutions(postorder is "symmetric" to the preorder)


  • 1

    I have noticed that the postorder traversal is left-right symmetric to the preorder traversal!
    Thus, when conducting postorder traversal, you first visit parent node, then the right child tree, last the left child tree.
    However, to get a right answer, you need to inverse the result!
    I have tested the code on OJ, they are accepted!

    Iterative Traversal

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> nums;
        stack<TreeNode* > stnode;
        while (root || !stnode.empty()) {
            if (!root) {
                root = stnode.top();
                stnode.pop();
            }
            nums.push_back(root->val);
            if (root->left) stnode.push(root->left);
            root = root->right;
        }
        return vector<int>(nums.rbegin(), nums.rend()) 
    } 
    

    Morris Traversal

    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            vector<int> nums;
            TreeNode* cur = nullptr;
    
            while (root) {
                if (root->right) {
                    cur = root->right;
                    while (cur->left && cur->left != root) {
                        cur = cur->left;
                    }
                    if (cur->left == root) {
                        cur->left = nullptr;
                        root = root->left;
                    } else {
                        nums.push_back(root->val);
                        cur->left = root;
                        root = root->right;
                    }
                } else {
                    nums.push_back(root->val);
                    root = root->left;
                }
            }
            return vector<int>(nums.rbegin(), nums.rend());
        } 
    }
    

    You can see the summary of all methods at here: http://blog.csdn.net/yc461515457/article/details/78082042


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.