[OJ.leetcode] binary-tree-preorder-traversal

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

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?

/* 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; } };