美文网首页
Binary Tree Preorder Traversal

Binary Tree Preorder Traversal

作者: 极速魔法 | 来源:发表于2017-06-28 21:07 被阅读2次
//144.Binary Tree preorder
struct Command{
    TreeNode* node;
    string s;
    Command(string s,TreeNode* node):s(s),node(node){}
};
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        
        if(root ==NULL){
            return res;
        }

        stack<Command> stack;
        stack.push(Command("go",root));
        while(!stack.empty()){
            Command com=stack.top();
            stack.pop();
            if(com.s=="print"){
//deal with recurision end condition
                res.push_back(com.node->val);
            } else{
                assert(com.s=="go");
//  not same order compared recurison
                if(com.node->right){
                    stack.push(Command("go",com.node->right));
                }
                if(com.node->left){
                    stack.push(Command("go",com.node->left));
                }
                stack.push(Command("print",com.node));
            }
        }

        return res;
    }
};

相关文章

网友评论

      本文标题:Binary Tree Preorder Traversal

      本文链接:https://www.haomeiwen.com/subject/jzkpcxtx.html