Tuesday, August 4, 2015

突击刷题： tree pre/in/post order traversal non-recusive

以前写过了，这里再写一下。其实这也是iterator的基础

pre-order



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: Preorder in vector which contains node values.
     */
    vector<int> preorderTraversal(TreeNode *root) {
        // write your code here
        vector<int> result;
        if (!root)
            return result;
        stack<TreeNode*> stk;
        stk.push(root);
        while(!stk.empty()){
            TreeNode* node=stk.top();
            stk.pop();
            result.push_back(node->val);
            if (node->right)
                stk.push(node->right);
            if (node->left)
                stk.push(node->left);
        }
        return result;
    }
};

inorder


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Inorder in vector which contains node values.
     */
public:
    vector<int> inorderTraversal(TreeNode *root) {
        // write your code here
        vector<int> result;
        stack<TreeNode*> stk;
        while(root || !stk.empty()){
            if (root){
                stk.push(root);
                root=root->left;
            } else{
                root=stk.top();
                result.push_back(root->val);
                stk.pop();
                root=root->right;
            }
        }
        
        return result;
    }
};

post order最不好理解，看了yu's coding garden， 引用在这里

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

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 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;
    }
};
Posted by at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)