leetcode Question: Binary Tree Postorder Traversal (iteration)

Binary Tree Postorder Traversal (iteration)

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

Analysis:

Classical problem,  the recursion version of the solution can be easily found by modifying here. In this post, I solved it iteratively.  Which data structure do remind us ?  Yes! Still stack!

The algorithm has following steps, which is slight different from the previous question:
(1) Push the root node into the stack.
(2) while the stack is not empty, do:
       if 
          the top node is a leaf node (no left&right children), pop it.
          or if the top node has been visited, pop it. (here we use a sign head to show the latest popped node, if the top node's child = the latest popped node, either left or right, it must has been visited.)
       else
          b. push the right child of the top node (if exists)
          c. push the left child of the top node (if exists)

Code (C++):

/**
 * Definition for binary tree
 * 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) {
        stack<TreeNode*> st;
        vector<int> res;
        if (!root){return res;}
        st.push(root);
        TreeNode* head=root;
        while (!st.empty()){
            TreeNode* top = st.top();
            if ((top->left==NULL && top->right==NULL)||top->right==head || top->left==head){
                res.push_back(top->val);
                st.pop();
                head = top;
            }else{
                if (top->right!=NULL){st.push(top->right);}
                if (top->left!=NULL){st.push(top->left);}
            }
        }
        return res;
    }
};

Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def postorderTraversal(self, root):
        res = []
        st = []
        if root != None:
            st.append([root,False])
            while len(st) != 0:
                tmp = st[-1]
                if tmp[1] == True:
                    res.append(st.pop()[0].val)
                elif tmp[0].left == None and tmp[0].right == None:
                    res.append(st.pop()[0].val)
                else:
                    st[-1][1] = True
                    if tmp[0].right != None:
                        st.append([tmp[0].right, False])
                    if tmp[0].left != None:
                        st.append([tmp[0].left, False])
        return res
        
        

        

leetcode Question: Binary Tree Preorder Traversal (iteration)

Binary Tree Preorder Traversal (iteration)

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

Analysis:

Classical problem,  the recursion version of the solution can be found here (you need do slight modification, can you do that?) . In this post, I solved it iteratively.  Which data structure do remind us ?  Yes! Stack!

The algorithm has following steps:
(1) Push the root node into the stack.
(2) while the stack is not empty, do:
       a. pop the top node and print it.
       b. push the right child of the top node (if exists)
       c. push the left child of the top node (if exists)

Code(C++):

/**
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        stack<TreeNode*> st;
        vector<int> res;
        if (!root){return res;}
        st.push(root);
        TreeNode* head=root;
        while (!st.empty()){
            TreeNode* top = st.top();
            res.push_back(top->val);
            st.pop();
            if (top->right!=NULL){st.push(top->right);}
            if (top->left!=NULL){st.push(top->left);}
        }
        return res;
    }
};

Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def preorderTraversal(self, root):
        res = [] 
        st = []
        if root != None:
            st.append(root)
            while len(st) != 0:
                tmp = st.pop()
                res.append(tmp.val)
                if (tmp.right != None):
                    st.append(tmp.right)
                if (tmp.left != None):
                    st.append(tmp.left)
        return res