LeetCode每日一题 (47)144. 二叉树的前序遍历

144. 二叉树的前序遍历

非递归：

1class Solution {
2   
3   
4   
5public:
6    vector<int> preorderTraversal(TreeNode* root) {
7   
8   
9   
10        vector<int> result;
11        TreeNode *p=root;
12        stack<TreeNode*> S;
13        while(p!=nullptr || !S.empty()){
14   
15   
16   
17            if(p!=nullptr){
18   
19   
20   
21                result.push_back(p->val);
22                S.push(p);
23                p=p->left;
24            }
25            else{
26   
27   
28   
29                p=S.top();
30                S.pop();
31                p=p->right;
32            }
33        }
34        return result;
35    }
36};

递归：

1class Solution {
2   
3   
4   
5public:
6    vector<int> preorderTraversal(TreeNode* root) {
7   
8   
9   
10        vector<int> result;
11        if(root==nullptr) return result;
12        result.push_back(root->val);
13        vector<int> temp;
14        temp=preorderTraversal(root->left);
15        result.insert(result.end(),temp.begin(),temp.end());
16        temp=preorderTraversal(root->right);
17        result.insert(result.end(),temp.begin(),temp.end());
18        return result;
19    }
20};

本文同步分享在 博客“战 胜”（CSDN）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。