binary-tree-preorder-traversal

gistfile1.txt

https://oj.leetcode.com/problems/binary-tree-preorder-traversal/

/*
preorder를 loop로 구현하기 위해서 stack을 이용하여 실제 recursive call과 함수 콜스택의 동작을 모방하여 그대로 적용하면 될것.
loop로 구현시, 실제로 return 시 스택에서 unwinding(pop)을 하여 이전 제어 상태 다음으로 제어가 넘어가야되는 부분을 구현하는 것이 어려운데, 간단히 flag 를 하나두어 unwinding 중인지 아닌지를 구분하도록 구현하면 간단.
        
*/

/**
 * 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) {
        vector<int> res;
        stack<TreeNode*> st;
        bool unwinding = false;
        TreeNode* node = root;
        
        if(root == NULL) return res;
        
        while(1) {
            if(node == NULL) {
                if(st.empty()) {
                    break;
                }
                
                node = st.top();
                st.pop();
                
                unwinding = true;
            }
            
            if(unwinding == false) {
                st.push(node);
                res.push_back(node->val);
                node = node->left;
            } else {
                node = node->right;
                unwinding = false;
            }
        }      
       
        return res;
    }
};