LeetCode/solutions/144. Binary Tree Preorder Traversal.md

# [144. Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/)
# 思路 
要求进行二叉树的前序遍历, 属于务必掌握的基本题目。
## 思路一 递归
最简单的当然就是递归遍历了, 先遍历当前节点, 再递归遍历左子树, 再递归遍历右子树. 递归出口就是当前节点为空.

## 思路二 迭代
稍微难一点的就是迭代遍历. 这里一共有三种写法, 注意领会相互区别，关键点就是**右孩子比左孩子先入栈**。

# C++
## 思路一 递归
``` C++
class Solution {
private:
    void helper(vector<int>&res, TreeNode *root){
        if(!root) return;
        res.push_back(root -> val);
        helper(res, root -> left);
        helper(res, root -> right);
    }
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector< int>res;
        helper(res, root);
        return res;
    }
};
```

## 思路二 迭代

### 写法一
``` C++
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) return res;
        stack<TreeNode*> stk{{root}}; // 注意这种初始化方法
        TreeNode *p;
        while (!stk.empty()) {
            p = stk.top(); 
            stk.pop();
            
            res.push_back(p -> val); // 先访问
            if(p -> right) stk.push(p -> right); // 再将右子树入栈
            if(p -> left) stk.push(p -> left);
        }
        return res;
    }
};
```


### 写法二
``` C++
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int>res;
        if(!root) return res;
        
        TreeNode *p = root;
        stack<TreeNode *>stk;
        while(!stk.empty() || p){
            if(!p){ // 向左下降不动了, 从栈顶pop元素
                p = stk.top();
                stk.pop();
            }
            
            res.push_back(p -> val);
            if(p -> right) stk.push(p -> right); 
            p = p -> left;
        }
        return res;
    }
};
```


### 写法三
``` C++
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int>res;
        if(!root) return res;
        
        TreeNode *p;
        stack<TreeNode *>stk;
        stk.push(root);
        while(!stk.empty()){
            p = stk.top();
            stk.pop();
            
            while(p){ // 一路向左下降
                res.push_back(p -> val);
                if(p -> right) stk.push(p -> right); 
                p = p -> left;
            }
        }
        return res;
    }
};
```