Problem Description

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?

 

Problem Solution

递归&非递归方案

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {private:    vector
     
       retVec; // the traversal sequence of outputpublic:    void recursiveTraverse(TreeNode *root){        if(root == NULL)            return;        retVec.push_back(root->val);        recursiveTraverse(root->left);        recursiveTraverse(root->right);    }    void iterTraverse(TreeNode *root){        if(root==NULL)            return;        stack
      
        st;        TreeNode* temp;        st.push(root);        while(!st.empty())        {            temp=st.top();            retVec.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) {     //   recursiveTraverse(root);        iterTraverse(root);        return retVec;    }};