Binary Tree Traverse

Leetcode Tree traverse problem

Given a binary tree, return the inorder, postorder and preorder traversal of its nodes’ values.
There are three solutions to the giving problem : 1) Recursive 2) Iterative 3) Morris
Morris solution is quite same for inorder and preorder but some kind of different for the postorder.

Inorder

Three ways to traverse the binary tree :
1) recursive time: O(N) space: O(N)

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        helper(root,res);
        return res;
    }
    void helper(TreeNode* root, vector<int>&res){
        if (!root) return;
        helper(root->left,res);
        res.push_back(root->val);
        helper(root->right,res);
    }
};

2) iterative time: O(N) space: O(N)

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(!root) return {};
        vector<int> res;
        stack<TreeNode*> st;
        auto cur = root;
        while(cur){
            st.push(cur);
            cur = cur->left;
        }
        while(!st.empty()){
            cur = st.top();
            st.pop();
            res.push_back(cur->val);
            cur = cur->right;
            while(cur){
                st.push(cur);
                cur = cur->left;
            }
        }
        return res;
    }
};

merge two while

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(!root) return {};
        vector<int> res;
        stack<TreeNode*> st;
        auto cur = root;
        while(cur || !st.empty()){
            if (cur){
                st.push(cur);
                cur = cur->left;
            }else{
                cur = st.top();
                st.pop();
                res.push_back(cur->val);
                cur = cur->right;
            }
        }
        return res;
    }
};

3) morris traversal time: O(N) space: O(1)

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(!root) return {};
        vector<int> res;
        auto cur = root;
        while(cur){
            if (!cur->left){
                res.push_back(cur->val);
                cur = cur->right;
            }else{
                auto pred = findPred(cur);
                if (!pred->right){
                    pred->right = cur;
                    cur = cur->left;
                }else{
                    pred->right = nullptr;
                    res.push_back(cur->val);
                    cur = cur->right;
                }
            }
        }
        return res;
    }
    inline auto findPred(TreeNode* root) -> TreeNode*{
        auto cur = root->left;
        while(cur->right && cur->right!= root){
            cur = cur->right;
        }
        return cur;
    }
};

Preorder

1) Recursive solution

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        helper(root,res);
        return res;
    }
    void helper(TreeNode* root,vector<int> &res){
        if (!root) return;
        res.push_back(root->val);
        helper(root->left,res);
        helper(root->right,res);
    }
};

2) Iterative solution

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        auto cur = root;
        while(cur || !st.empty()){
            if (cur){
                res.push_back(cur->val);
                st.push(cur);
                cur = cur->left;            
            }else{
                cur = st.top();
                st.pop();
                cur = cur->right;
            }
        }
        return res;
    }
};

3) Morris traversal

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        auto cur = root;
        while(cur){
            res.push_back(cur->val);
            if (!cur->left){
                cur = cur->right;
            }else{
                auto pred = findPred(cur);
                if(!pred->right){
                    pred->right = cur;
                    cur = cur->left;
                }else{
                    pred->right = nullptr;
                    res.pop_back();
                    cur = cur->right;
                }
            }
        }
        return res;
    }
    inline auto findPred(TreeNode* node)-> TreeNode*{
        auto cur = node->left;
        while(cur->right && cur->right != node){
            cur = cur->right;
        }
        return cur;
    }
};

晚点补充postorder的三种方法，先吃鸡！

1) etc

2) Iterative solution

Use a point node to avoid repeat traverse

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        auto cur = root;
        TreeNode* lastNode = nullptr;
        while(cur || !st.empty()){
            if (cur){
                st.push(cur);
                cur = cur->left;
            }else{
                auto top = st.top();
                if(top->right && top->right != lastNode){
                    cur = top->right;
                }else{
                    res.push_back(top->val);
                    lastNode = top;
                    st.pop(); 
                }
            }
        }
        return res;
    }
};

3) Morris solution
A little bit tricky since we need use a dummy root to perform this algorithm.

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        auto dump = new TreeNode(0);
        dump->left = root;
        auto cur = dump;
        while(cur){
            if (cur->left){
                auto pred = cur->left;
                while(pred->right && pred->right != cur)
                    pred = pred->right;
                if(!pred->right){
                    pred->right = cur;
                    cur = cur->left;
                }else{
                    pred->right = nullptr;
                    ReverseAdd(res,cur->left,pred);
                    cur = cur->right;
                }
            }else{
                cur = cur->right;
            }
        }
        return res;
    }
    
    void ReverseAdd(vector<int>&res,TreeNode* from, TreeNode* to){
        auto it_end = res.end();
        int sz = res.size(); 
        while(true){
            res.insert(it_end,from->val);
            if(from == to) break;
            from = from->right;
            it_end = res.begin() + sz;
        }
    }
    
};