###### tags: `Leetcode` `easy` `tree` `python` `c++`

# 144. Binary Tree Preorder Traversal

## [題目出處:] https://leetcode.com/problems/binary-tree-preorder-traversal/

## 題目:
Given the root of a binary tree, return the preorder traversal of its nodes' values.

**Follow up: Recursive solution is trivial, could you do it iteratively?**

## 解題想法:
##### 參考 [94. Binary Tree Inorder Traversal]https://hackmd.io/@Hungen/HJ5n2VI1j
Preorder: (中)左右
* 迭代:
* Step1: 每當遇到root直接將其val加到最終res
* Step2: stack存入root, root=root.left
* Step3: 當root==None
* Step4: cur=stack.pop()
* Step5: 新root=cur.right 重複 Step1

## Python ( Recursive & Iterative ):

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class SolutionRe():
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        self.res=[]
        self.dfs(root)
        return self.res
    def dfs(self,root):
        if not root:
            return 
        self.res.append(root.val)
        self.dfs(root.left)
        self.dfs(root.right)

class SolutionIt:
    def preorderTraversal(self,root):
        stack=[]
        res=[]
        while root or stack:
            if root:
                res.append(root.val)
                stack.append(root)
                root=root.left
            else:
                cur=stack.pop()
                root=cur.right
        return res
                

root=TreeNode(1)
root.insertRight(2)
root.right.insertLeft(3)
print("Original:",end=" ")
root.printTree()

Recursive=SolutionRe()
re=Recursive.preorderTraversal(root)
print("Recursive: ",re)

Iterative=SolutionIt()
it=Iterative.preorderTraversal(root)
print("Iterative: ",it)

## C++ ( Recursive & Iterative ):

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
using namespace std;

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(): val(0), left(nullptr), right(nullptr){}
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};

void InsertLeft(TreeNode* root, int data){
    TreeNode* tmp=root;
    if (tmp->left)
        InsertLeft(tmp->left,data);
    else{
        TreeNode* new_node=new TreeNode(data);
        tmp->left=new_node;
    }
}

void InsertRight(TreeNode* root, int data){
    TreeNode* tmp=root;
    if (tmp->right)
        InsertRight(tmp->right,data);
    else{
        TreeNode *new_node=new TreeNode(data);
        tmp->right=new_node;
    }
}

void PrintTree(TreeNode* root){
    TreeNode* tmp=root;
    vector<int> res;
    queue<TreeNode*> que;
    que.push(tmp);
    while(!que.empty()){
        TreeNode* cur=que.front(); que.pop();
        res.push_back(cur->val);
        if (cur->left)
            que.push(cur->left);
        if (cur->right)
            que.push(cur->right);
    }
    cout<<"Original Tree: ";
    for (int i=0; i<res.size(); i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;
}

class SolutionRe{
public:
    vector<int> preorderTraversal(TreeNode* root){
        vector<int> res;
        Traversal(root,res);
        return res;
    }
    void Traversal(TreeNode* root, vector<int>& res){
        if (!root)
            return;
        res.push_back(root->val);
        Traversal(root->left,res);
        Traversal(root->right,res);
    }
};

class SolutionIT{
public:
    vector<int> preorderTraversal(TreeNode* root){
        vector<int>res;
        stack<TreeNode*>tmp;
        while (root || !tmp.empty()){
            if (root){
                res.push_back(root->val);
                tmp.push(root);
                root=root->left;
            }
            else{
                TreeNode* cur=tmp.top(); tmp.pop();
                root=cur->right;
            }
        }
        return res;
    }
};

void PrintVector(vector<int>& nums){
    for (int i=0; i<nums.size(); i++){
        cout<<nums[i]<<" ";
    }
    cout<<endl;
}

int main(){
    TreeNode* root=new TreeNode(1);
    InsertRight(root,2);
    InsertLeft(root->right,3);
    PrintTree(root);

    SolutionRe Recursive;
    vector<int> re=Recursive.preorderTraversal(root);
    cout<<"Preorder: ";
    PrintVector(re);

    SolutionIT Iterative;
    vector<int> it=Iterative.preorderTraversal(root);
    cout<<"Preorder: ";
    PrintVector(it);

    return 0;
}