My clean Morris traversal solution with C++


  • 0
    Y
    /**
     * 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:
        vector<int> postorderTraversal(TreeNode* root) {
            vector<int> reval;
            TreeNode dummy(0);
            dummy.left = root;
            root = & dummy;
            while(root){
                if(root->left){
                    TreeNode *pred(root->left);
                    while(pred->right && pred->right!=root){
                        pred = pred->right;
                    }
                    if(pred->right!=root){
                        //first time access current node
                        pred->right = root;
                        root = root->left;
                    } else {
                        //second time access current node
                        pred->right = nullptr;//revert back
                        backward_insert(root->left,reval);
                        root = root->right;
                    }
                } else {
                    root = root->right;
                }
            }
            return reval;
        }
    private:
        void backward_insert(TreeNode* root,vector<int> & reval){
            if(!root) return;
            backward_insert(root->right,reval);
            reval.push_back(root->val);
        }
    };
    

  • 1
    A

    @yang121 This is still recursive. Yet the problem explicitly says no recursive. The traversal is basically smoke and mirrors. The core logic is the right branch recursion call of "backward_insert()".


  • 0
    Y

    @ayuanx
    sorry, my bad.
    Changed the code.

    /**
     * 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:
        vector<int> postorderTraversal(TreeNode* root) {
            vector<int> reval;
            TreeNode dummy(0);
            dummy.left = root;
            root = & dummy;
            while(root){
                if(root->left){
                    TreeNode *pred(root->left);
                    while(pred->right && pred->right!=root){
                        pred = pred->right;
                    }
                    if(pred->right!=root){
                        //first time access current node
                        pred->right = root;
                        root = root->left;
                    } else {
                        //second time access current node
                        pred->right = nullptr;//revert back
                         
                        TreeNode *temp(root->left);
                        vector<int> vec;
                        while(temp){
                            vec.push_back(temp->val);
                            temp = temp->right;
                        }
                        reval.insert(reval.end(),vec.rbegin(),vec.rend());
    					
                        root = root->right;
                    }
                } else {
                    root = root->right;
                }
            }
            return reval;
        }
    };
    

Log in to reply
 

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