Given a binary tree, return the preorder traversal of its nodes' values.

Given binary tree {1,#,2,3},

　 1

　　\

　　 2

　　/

　 3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

如下是非递归版本。

void preorderNonRecursiveTraversal(TreeNode*pRoot, vector
     
      & result)    {        if (pRoot == NULL) return;        stack
      
        st;        TreeNode* temp;        st.push(pRoot);        while (!st.empty())        {            temp = st.top();            result.push_back(temp->val);            st.pop();            if (temp->right != NULL)st.push(temp->right);//先右 后左            if (temp->left != NULL)st.push(temp->left);        }    }    vector
       
         preorderTraversal(TreeNode* root)    {        vector
        
          result;        if (root == NULL) return result;        preorderNonRecursiveTraversal(root, result);        return result;    }
        
       
      
     

 递归版本：

void PreOrder(TreeNode* pRoot, vector
     
      & result)    {        if (pRoot != NULL)        {            result.push_back(pRoot);            PreOrder(pRoot->left, result);                        PreOrder(pRoot->right, result);        }    }