144. 二叉树的前序遍历

给定一个二叉树，返回它的前序遍历。

Solution1（递归版）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preorder(root,res);
        return res;
    }
    void preorder(TreeNode* node, vector<int> &res){
        if(!node) return;
        res.push_back(node->val);
        preorder(node->left, res);
        preorder(node->right, res);
    }
    
};

Solution2（迭代版）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if(!root) return res;
        stack<TreeNode*> s;
        TreeNode* cur = root;
        s.push(root);
        while(!s.empty()){
            cur = s.top();
            s.pop();
            res.push_back(cur->val);
            if(cur->right) s.push(cur->right);
            if(cur->left) s.push(cur->left);
                
        }
        return res;
    }
};

前序遍历的顺序为先处理当前节点，再处理左节点，最后处理右节点。

对于栈来说。首先处理当前节点。然后先把右节点压入栈中，转而处理左节点。

OR

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> toVisit;
        vector<int> result;
        if(root == NULL){
            return result;
        }
        TreeNode* current = root;
        while(current || !toVisit.empty()){
            if(current != NULL){
                result.push_back(current->val);
                toVisit.push(current->right);
                current = current->left;
            } else {
                current = toVisit.top();
                toVisit.pop();
            }
        }
        return result;
    }
};