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].


返回[1,2,3]


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


=》注意：递归的算法是很普通，能不能不要递归呢？


[cpp] view plaincopy
/** 
 * Definition for binary tree 
 * struct TreeNode { 
 *     int val; 
 *     TreeNode *left; 
 *     TreeNode *right; 
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
 * }; 
 */  
class Solution {  
public:  
    vector preorderTraversal(TreeNode *root) {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
          
    }  
};  


 


晓东解析：


这个题目用递归来实现的确很简单，就是先遍历左，再遍历右。那非递归的算法就是先一直左到底，并把这些所有的左都压到一个栈里面，然后到最后，再一个个pop出来，每pop一个，对它的右子树再进行一次类似的遍历就可以了。


 


代码实现：


1、递归实现


[cpp] view plaincopy
/** 
* Definition for binary tree 
* struct TreeNode { 
*     int val; 
*     TreeNode *left; 
*     TreeNode *right; 
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
* }; 
*/  
class Solution {  
public:  
    vector preorderTraversal(TreeNode *root) {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
        vector result;  
        vector left;  
        vector right;  
          
        if(root == NULL) return result;  
        result.push_back(root->val);  
        left = preorderTraversal(root->left);  
        right = preorderTraversal(root->right);  
          
        if(left.size() != 0)  
            result.insert(result.end(), left.begin(), left.end());  
        if(right.size() != 0)  
            result.insert(result.end(), right.begin(), right.end());  
          
        return result;  
          
    }  
};  




运行结果：


67 / 67test cases passed.
Status:
Accepted
Runtime: 20 ms
 


2、非递归实现：


[cpp] view plaincopy
/** 
 * Definition for binary tree 
 * struct TreeNode { 
 *     int val; 
 *     TreeNode *left; 
 *     TreeNode *right; 
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
 * }; 
 */  
class Solution {  
public:  
    vector preorderTraversal(TreeNode *root) {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
        stack TreeStack;  
        vector result;  
          
        if(root == NULL) return result;  
          
        while(root || !TreeStack.empty()){  
            while(root){  
                TreeStack.push(root);  
                result.push_back(root->val);  
                root = root->left;  
            }  
            root = TreeStack.top();  
            TreeStack.pop();  
            root = root->right;  
        }  
          
    }  
};  


运行结果：


67 / 67test cases passed.


Status:


Accepted


Runtime: 12 ms