Summary of Iterative Tree Traversal Solution & KMP


  • 2
    F

    Post-order

    //post order iterative traversal
    vector<int> postorderTraversal(TreeNode* root) {
    	vector<int> ans;
    	if (!root) return ans;
    	stack<TreeNode*> nodes;
    	TreeNode* pre = nullptr;
    	nodes.push(root);
    	while (!nodes.empty()) {
    		root = nodes.top();
    		if ((root->left == nullptr) && (root->right == nullptr) ||
    				(pre != nullptr && (root->left = pre || root->right == pre))) {
    			ans.push_back(root->val);
    			nodes.pop();
    			pre = root;
    		}
    		else {
    			if (root->right) nodes.push(root->right);
    			if (root->left) nodes.push(root->left);
    		}
    	}
    }
    

    In-Order

    //in order iterative traversal
    vector<int> inorderTraversal(TreeNode* root) {
    	vector<int> ans;
    	stack<TreeNode*> nodes;
    	while (root || !nodes.empty()) {
    		while (root) {
    			nodes.push(root);
    			root = root->left;
    		}
    		if (!nodes.empty()) {
    			root = nodes.top();
    			nodes.pop();
    			ans.push_back(root->val);
    			root = root->right;
    		}
    	}
    }
    

    Pre-Order

    //pre order iterative traversal
    vector<int> pre-orderTraversal(TreeNode* root) {
    	vector<int> ans;
    	if (!root) return ans;
    	stack<TreeNode*> nodes;
    	nodes.push(root);
    	while (!nodes.empty()) {
    		root = nodes.top();
    		nodes.pop();
    		ans.push_back(root->val);
    		if (root->right) nodes.push(root->right);
    		if (root->left) nodes.push(root->left);
    	}
    	return ans;
    }
    

  • 0
    F

    Easy to grasp in-order solution

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

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

  • 0
    F

    Tricky Post-order Solution :

    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            stack<TreeNode*> st;
            vector<int> result;
            if(!root) return result;
            st.push(root);
            while (!st.empty()) {
                TreeNode* cur = st.top();
                st.pop();
                result.push_back(cur->val);
                if (cur->left) st.push(cur->left);
                if (cur->right) st.push(cur->right);
            }
            reverse(result.begin(), result.end());
            return result;
        }
    };
    
    

  • 0
    F

    Post Order Solution

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

  • 0
    F

    Important !!!
    In fact, my classmates meet this problem when google onsite, but it requires that you can not use DFS and level by level BFS. So you should consider some traversal based solution to get the max depth of the binary tree.

    Here is a concise implementation, you just can draw and run some cases and you will grasp it quickly !!!

    
    class Solution {
    public:
        int maxDepth(TreeNode* root) {
            if (!root) return 0;
            stack<TreeNode*> s;
            s.push(root);
            int result = 0;
            TreeNode* prev = nullptr;
            while (!s.empty()) {
            	TreeNode* cur = s.top();
            	if (!prev || prev->left == cur || prev->right == cur) {
            		if (cur->left) {
            			s.push(cur->left);
            		}
            		else if (cur->right) {
            			s.push(cur->right);
            		}
            	}
            	else if (cur->left == prev) {
            		if (cur->right) 
            			s.push(cur->right);
            	} else {
            		s.pop();
            	}
            	prev = cur;
            	if (s.size() > result) {
            		result = s.size();
            	}
            }
            return result;
        }
    };

  • 0
    F

    KMP solution offered by fff

    class Solution {
    public:
        vector<int> getNext(string needle) {
            if (needle.size() == 0) return vector<int>();
            vector<int> next(needle.size()+1);
            int i = 0; 
            int j = -1;
            next[i] = j;
            while (i < needle.size()) {
                while (j != -1&& needle[i]!=needle[j]) j = next[j];
                next[++i] = ++j;
            }
            return next;
        }
        int strStr(string haystack, string needle) {
            if (needle == "") return 0;
            if (haystack == "") return -1;
            if (needle.size() > haystack.size()) return -1;
            vector<int> next = getNext(needle);
            int i = 0;
            int j = 0;
            while (i < haystack.size()) {
                while (j != -1 && haystack[i] != needle[j]) j = next[j];
                i ++;
                j ++;
                if (j == needle.size()) {
                    return i - j;
                }
            }
            return -1;
        }
    };
    

Log in to reply
 

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