美文网首页
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