1 class Solution {
 2 public:
 3     vector<int> preorderTraversal(TreeNode* root) {
 4         vector<int> ans;
 5         if(root){
 6             TreeNode* temp;
 7             stack<TreeNode*> s;                 //利用栈，每次打印栈顶，然后将栈顶弹出
 8             s.push(root);
 9             while(!s.empty()){
10                 temp=s.top();
11                 ans.push_back(temp->val);
12                 s.pop();
13                 if(temp->right)s.push(temp->right);    //弹出的栈顶存在temp中，如果有右节点，先放右节点，再放左节点，这样左节点就在上面
14                 if(temp->left)s.push(temp->left);
15             }
16         }
17         return ans;
18     }
19 };

递归实现：

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 private: 
12     vector<int> ans;
13 public:
14     vector<int> preorderTraversal(TreeNode* root) {
15         if(root){
16             ans.push_back(root->val);
17             preorderTraversal(root->left);
18             preorderTraversal(root->right);
19         }
20         return ans;
21     }
22 };

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。