morris traverse post order


  • 0
    A
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* reverse(TreeNode* root) {
            TreeNode* l = nullptr;
            while (root) {
                auto tmp = root;
                root = root->right;
                tmp->right = l;
                l = tmp;
            }
            return l;
        }
        
        vector<int> postorderTraversal(TreeNode* root) {
            
            TreeNode* proot = new TreeNode(0);
            proot->left = root;
            root = proot;
            vector<int> ret;
            while (root) {
                auto l = root->left;
                if (l) {
                    while (l->right && l->right != root) {
                        l = l->right;
                    }
                    // go left
                    if (l->right == nullptr) {
                        l->right = root;
                        root = root->left;
                    } else { // back from left
                        l->right = nullptr;
                        auto h = reverse(root->left);
                        while (h) {
                            ret.push_back(h->val);
                            h = h->right;
                        }
                        reverse(l);
                        root = root->right;
                    }
                } else { // no left
                    root = root->right;    
                }
            }
            return ret;
        }
    };
    

Log in to reply
 

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