#include <iostream>
#include <vector>
#include <stack>

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

//递归法
void traveral(BinaryTreeNode*cur, std::vector<int>&nums)
{
    if (cur == nullptr)
    {
        std::cout << "cur is null" << std::endl;
        return;
    }
    else{
        std::cout << "cur node: " << cur->val << ", ";
        nums.push_back(cur->val);
        std::cout << "traveral left" << ", ";
        traveral(cur->left, nums);
        std::cout << "traveral right" << ", ";
        traveral(cur->right, nums);
    }
}


std::vector<int> PreorderTraversalRecursion(BinaryTreeNode* root)
{
    std::vector<int> result;
    traveral(root, result);
    return result;
}

//迭代法
std::vector<int> PreorderTraversalIterator(BinaryTreeNode* root)
{
    std::stack<BinaryTreeNode*> st;
    std::vector<int> result;
    if (root == nullptr)
    {
        return result;
    }

    st.push(root);//root进栈
    while (!st.empty())
    {
        BinaryTreeNode* node = st.top();//根

        st.pop();//弹出
        result.push_back(node->val);//当前节点值
        if (node->right)
        {
            st.push(node->right);//右节点
        }
        if (node->left)
        {
            st.push(node->left);//左节点
        }
    }
    return result;
}

int main()
{
    BinaryTreeNode *nodeOne = new BinaryTreeNode(1);
    BinaryTreeNode *nodeTwo = new BinaryTreeNode(2);
    BinaryTreeNode*nodeThree = new BinaryTreeNode(3);
    BinaryTreeNode*nodeFour = new BinaryTreeNode(4);
    BinaryTreeNode*nodeFive = new BinaryTreeNode(5);
    BinaryTreeNode*nodeSix = new BinaryTreeNode(6);

    //       1
   //      2   3
  //      4 5
 //          6
//1-2-4-5-6-3
    nodeOne->left = nodeTwo;
    nodeOne->right = nodeThree;

    nodeTwo->left = nodeFour;
    nodeTwo->right = nodeFive;

    nodeFive->right = nodeSix;

    std::vector<int>resultsRecursion;
    resultsRecursion = PreorderTraversalRecursion(nodeOne);
    for (std::vector<int>::iterator it = resultsRecursion.begin(); it != resultsRecursion.end(); it++)
    {
        std::cout << (*it) << ", ";
    }

    std::cout << std::endl<< "-------------------------------------" << std::endl;
    std::vector<int>resultsIteration;
    resultsIteration = PreorderTraversalIterator(nodeOne);
    for (std::vector<int>::iterator it = resultsIteration.begin(); it != resultsIteration.end(); it++)
    {
        std::cout << (*it) << ", ";
    }
}