leetcode:binary-tree-preorder-traversal-白红宇

leetcode:binary-tree-preorder-traversal

阅读量：4180 次

发布时间：2019-05-26

本文共 1015 字，大约阅读时间需要 3 分钟。

题目描述：

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.递归方式

class Solution {public:    void PreOrder(TreeNode *root,vector
   
    & vc)//注意这里一定是传递引用，不是传递值        {        if(root!=NULL)            {            vc.push_back(root->val);            PreOrder(root->left,vc);            PreOrder(root->right,vc);        }                 }    vector
    
      preorderTraversal(TreeNode *root) {        vector
     
       vc;        PreOrder(root,vc);        return vc;             }};

2.非递归方式


   
    
     
                     
         
          
           class 
           Solution {
          
          
           public
           :
          
          
               
           vector<
           int
           > preorderTraversal(TreeNode *root) {
          
          
                   
           vector<
           int
           > vc;
          
          
                   
           stack
            
              mystack;
            
          
          
                    
           if 
           (root == NULL){
          
          
                       
           return 
           vc;
          
          
                   
           }
          
          
                   
           mystack.push(root);
          
          
                   
           while
           (!mystack.empty())
          
          
                      
           {
          
          
                       
           TreeNode *temp=mystack.top();
          
          
                       
           vc.push_back(temp->val);
          
          
                       
           mystack.pop();
          
          
                       
           if
           (temp->right!=NULL)
          
          
                           
           mystack.push(temp->right);
          
          
                       
           if
           (temp->left!=NULL)
          
          
                           
           mystack.push(temp->left);
          
          
                   
           }
          
          
                   
           return 
           vc;
          
          
                    
          
          
               
           }
          
          
           };