前言

【LeetCode 题解】系列传送门：

1.题目描述

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?

2. 题意

先序遍历二叉树，递归的思路是普通的，能否用迭代呢？

3. 思路

非递归思路：<借助stack>

vector
     
       preorderTraversal(TreeNode *root) {        stack
      
        st;        vector
       
         vi;        vi.clear();        if(!root) return vi;                st.push(root);        while(!st.empty()){            TreeNode *tmp = st.top();            vi.push_back(tmp->val);                st.pop();            if(tmp->right) st.push(tmp->right);            if(tmp->left) st.push(tmp->left);        }        return vi;    }

递归思路：

class Solution {private:    vector
     
       vi;public:    vector
      
        preorderTraversal(TreeNode *root) {        vi.clear();        if(!root) return vi;        preorder(root);return vi;    }    void preorder(TreeNode* root){        if(!root) return;        vi.push_back(root->val);        preorder(root->left);        preorder(root->right);    }};