###### tags: `Leetcode` `easy` `tree` `python` `c++` `Top 100 Liked Questions`

# 94. Binary Tree Inorder Traversal

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

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

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

## 解題想法:
Inorder: 左(中)右
* 迭代:
* step1: root一路往左子遍歷，依序存入stack直到root==None
* step2: pop出stack最頂的: 設為cur
* step3: 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 inorderTraversal(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.dfs(root.left)
        self.res.append(root.val)
        self.dfs(root.right)

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

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

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

Iterative=SolutionIt()
it=Iterative.inorderTraversal(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) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    };

void InsertLeft(TreeNode* root, int data){
    TreeNode *tmp=root;
    while (tmp->left != nullptr){
        tmp=tmp->left;
    }
    TreeNode *new_left = new TreeNode(data);
    tmp->left = new_left;
}

void InsertRight(TreeNode* root, int data){
    TreeNode *tmp=root;
    while (tmp->right != nullptr){
            tmp=tmp->right;
    }
    TreeNode *new_right = new TreeNode(data);
    tmp->right = new_right;
}

void printTree(TreeNode* root){
    TreeNode *tmp=root;
    queue<TreeNode *> que;
    vector<int> res;
    que.push(tmp);
    while ( !que.empty()){
        TreeNode * cur_root=que.front(); //get head
        que.pop();
        res.push_back(cur_root->val);
        if (cur_root->left != nullptr)
              que.push(cur_root->left);
        if (cur_root->right != nullptr)
              que.push(cur_root->right);
    }
    for (int i=0; i<res.size(); i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;

}

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

class SolutionIt {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> rootStack;
        vector<int> res;
        while (root!=nullptr || !rootStack.empty()){
            if (root){
                rootStack.push(root);
                root=root->left;
            }
            else{
                TreeNode *cur_root=rootStack.top();
                rootStack.pop();
                res.push_back(cur_root->val);
                root=cur_root->right;
            }
        }
        return res;
    }
};

int main(){
    TreeNode *root= new TreeNode(1);
    InsertRight(root,2);
    InsertLeft(root->right,3);
    cout<<"Original Tree:";
    printTree(root);

    SolutionRe res;
    vector<int> ans = res.inorderTraversal(root);
    cout<<"After Inorder_Recursive :";
    for (int i=0; i<ans.size(); i++){
        cout<<ans[i]<<" ";
    }
    cout<<endl;

    SolutionIt res2;
    vector<int> ans2 = res2.inorderTraversal(root);
    cout<<"After Inorder_Iterative :";
    for (int i=0; i<ans2.size(); i++){
        cout<<ans2[i]<<" ";
    }
    cout<<endl;
    return 0;
}