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

// 基础的树结构体
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int val) {
        this->val = val;
        this->left = NULL;
        this->right = NULL;
    }
};

// 用完记得 delete
TreeNode *constructTree() {
    TreeNode *node10 = new TreeNode(10);
    
    TreeNode *node5 = new TreeNode(5);
    TreeNode *node15 = new TreeNode(15);
    
    TreeNode *node4 = new TreeNode(4);
    TreeNode *node6 = new TreeNode(6);
    TreeNode *node14 = new TreeNode(14);
    TreeNode *node16 = new TreeNode(16);
    
    node10->left = node5;
    node10->right = node15;
    
    node5->left = node4;
    node5->right = node6;
    
    node15->left = node14;
    node15->right = node16;
    
    return node10;
}

// 打印 vector
void printVector(vector<int> &valVec) {
    for (int i = 0; i< valVec.size(); i++) {
        printf("%d ", valVec[i]);
    }
}


// 先序遍历（递归）
void preOrder(TreeNode *pRoot, vector<int> &valVec) {
    if (pRoot != NULL) {
        valVec.push_back(pRoot->val);
        preOrder(pRoot->left, valVec);
        preOrder(pRoot->right, valVec);
    }
}

// 先序遍历（非递归）
void preOrderNotRecursive(TreeNode *pRoot, vector<int> &valVec) {
    if (pRoot == NULL) {
        return;
    }

    stack<TreeNode *> sta;
    TreeNode *pNode = pRoot;
    while (pNode != NULL || sta.empty() == false) {
        if (pNode != NULL) {
            // 访问节点
            valVec.push_back(pNode->val);
            //先进栈再取做节点(等下可以回溯上一节点，取右节点)，一路向左
            sta.push(pNode);
            pNode = pNode->left;
        } else {
            // 左节点处理完，现在处理右节点
            pNode = sta.top();
            sta.pop();
            pNode = pNode->right;
        }
    }
}

// 中序遍历（递归）
void middleOrder(TreeNode *pRoot, vector<int> &valVec) {
    if (pRoot != NULL) {
        middleOrder(pRoot->left, valVec);
        valVec.push_back(pRoot->val);
        middleOrder(pRoot->right, valVec);
    }
}

// 中序遍历（非递归），跟先序遍历极度相似
void middleOrderNotRecursive(TreeNode *pRoot, vector<int> &valVec) {
    if (pRoot == NULL) {
        return;
    }
    
    stack<TreeNode *> sta;
    TreeNode *pNode = pRoot;
    while (pNode != NULL || sta.empty() == false) {   /// 判断条件跟先序遍历一样
        if (pNode != NULL) {  /// if语句可理解为跟先序遍历一样
            //先进栈再取做节点(等下可以回溯上一节点，取右节点)，一路向左
            sta.push(pNode);
            pNode = pNode->left;
        } else { /// else语句可理解为跟先序遍历一样
            pNode = sta.top();
            sta.pop();
            // 访问节点
            valVec.push_back(pNode->val);        /// 就这一行跟先序不一样，这行代码位置变了 ------------------------------------------
            // 左节点处理完，现在处理右节点
            pNode = pNode->right;
            
        }
    }
}


// 后续遍历（递归）
void backOrder(TreeNode *pRoot, vector<int> &valVec) {
    if (pRoot != NULL) {
        backOrder(pRoot->left, valVec);
        backOrder(pRoot->right, valVec);
        valVec.push_back(pRoot->val);
    }
}

// 后续遍历（非递归）
void backOrderNotRecursive(TreeNode *pRoot, vector<int> &valVec) {
    if (pRoot == NULL) {
        return;
    }
    
    stack<TreeNode *> sta;
    TreeNode *pNode = pRoot;
    TreeNode *lastVisitedNode = NULL;
    
    while (pNode != NULL || sta.empty() == false) { /// 判断条件跟先序、中序遍历一样
        if (pNode != NULL) { /// if语句可理解为跟先序、中序遍历一样
            sta.push(pNode);
            pNode = pNode->left;
        } else {
            // 局部根节点暂时不要出栈，因为可能存在右子树，需要处理完右子树后才能处理该节点
            pNode = sta.top();
            
            if (pNode->right != NULL && pNode->right != lastVisitedNode) {
                // 如果存在右节点，并且没有访问过
                pNode = pNode->right;
                sta.push(pNode);
                pNode = pNode->left;
            } else {
                // 访问节点
                valVec.push_back(pNode->val);
                // 此时可以出栈了
                sta.pop();
                
                lastVisitedNode = pNode;
                pNode = NULL;
            }
        }
    }
}


// 按层遍历
void levelOrder(TreeNode *pRoot, vector<int> &valVec) {
    if (pRoot != NULL) {
        deque<TreeNode *> deq;
        deq.push_back(pRoot);

        while (deq.empty() == false) {
            TreeNode *pNode = deq.front();
            deq.pop_front();
            valVec.push_back(pNode->val);
            
            if (pNode->left) {
                deq.push_back(pNode->left);
            }
            if (pNode->right) {
                deq.push_back(pNode->right);
            }
        }
    }
}


int main(int argc, const char * argv[]) {
    std::cout << "\n\nstart ----------";
    TreeNode *pRoot = constructTree();
    
    // 先序遍历（递归）
    std::cout << "\n\n先序遍历（递归）------ \n";
    vector<int> valVecPre;
    preOrder(pRoot, valVecPre);
    printVector(valVecPre);
    
    // 先序遍历（非递归）
    std::cout << "\n\n先序遍历（非递归）------ \n";
    vector<int> valVecPreNotRecursive;
    preOrderNotRecursive(pRoot, valVecPreNotRecursive);
    printVector(valVecPreNotRecursive);

    // 中序遍历（递归）
    std::cout << "\n\n中序遍历（递归）------ \n";
    vector<int> valVecMid;
    middleOrder(pRoot, valVecMid);
    printVector(valVecMid);
    
    // 中序遍历（非递归）
    std::cout << "\n\n中序遍历（非递归）------ \n";
    vector<int> valVecMidNotRecursive;
    middleOrderNotRecursive(pRoot, valVecMidNotRecursive);
    printVector(valVecMidNotRecursive);
    
    // 后序遍历（递归）
    std::cout << "\n\n后序遍历（递归）------ \n";
    vector<int> valVecBack;
    backOrder(pRoot, valVecBack);
    printVector(valVecBack);
    
    // 后序遍历（非递归）
    std::cout << "\n\n后序遍历（非递归）------ \n";
    vector<int> valVecBackNotRecursive;
    backOrderNotRecursive(pRoot, valVecBackNotRecursive);
    printVector(valVecBackNotRecursive);
    
    // 按层遍历
    std::cout << "\n\n按层遍历 ------ \n";
    vector<int> valVecLevel;
    levelOrder(pRoot, valVecLevel);
    printVector(valVecLevel);
    
    std::cout << "\n\nend ---------- \n\n";
    
    return 0;
}