leetcode-144-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?

二叉树前序遍历。

如果用递归做这道题很简单，这里本文提供一种非递归的解法。利用一个辅助栈，既然是先序遍历，那么右子树应该先入栈，接着是左子树。

/**
 * Definition for a binary tree node.
 * 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) {
            stack<TreeNode*> s;
            vector<int> res;
            while(!s.empty()||root)
                {

                    if(root)
                        {
                            res.push_back(root->val);
                            if(root->right)
                                s.push(root->right);
                            root=root->left;
                        }
                    else{
                            root=s.top();
                            s.pop();
                        }
                }
            return res;
        }
};