vector<TreeNode *> generateTrees(int n) {
	vector<TreeNode *> sub_tree = generateTrees(1, n);
	return sub_tree;
}

vector<TreeNode *> generateTrees(int low, int high) {
	vector<TreeNode *> result;
	if (low > high)
	{
		result.push_back(NULL);
		return result;
	}
	else if (low == high)
	{
		TreeNode *node = new TreeNode(low);
		result.push_back(node);
		return result;
	}
	
	for (int i=low; i<=high; i++)
	{
		vector<TreeNode *> left = generateTrees(low, i - 1);
		vector<TreeNode *> right = generateTrees(i + 1, high);
		for (int j=0; j<left.size(); j++)
		{
			for (int k=0; k<right.size(); k++)
			{
				TreeNode *root = new TreeNode(i);
				root->left = left[j];
				root->right = right[k];
				result.push_back(root);
			}
		}
	}
	return result;
}

/**
 * 图节点的邻接表表示形式
 */
struct GraphNode {
    std::string label;
    std::vector<GraphNode *> neighbors;
    bool visited;
    GraphNode(std::string x) : label(x), visited(false) {};
};

/**
 * 通过字符串的值，找到该字符串对应的图节点
 */ 
GraphNode *get_one_node(const std::vector<GraphNode *> &node_vector, std::string str)
{
    for (std::vector<GraphNode *>::const_iterator iter = node_vector.begin(); iter != node_vector.end(); iter++)
    {
        if ((*iter)->label == str)
        {
            return *iter;
        }
    }
    return NULL;
}

/**
 * 时间复杂度高,对图的构建一般效率要求较低
 * 对于查找某个节点的邻接点的指针操作可以使用map来提高查询效率
 * 或者可以通过不需要初始化所有节点的方式来构造图，而是采用需要哪个节点构造哪个节点的方式
 */
std::vector<GraphNode *> create_graph(std::string str)
{
    std::vector<GraphNode *> node_vector;
   
    // init all nodes
    for (size_t pos = 0; pos < str.length() - 1;)
    {
        size_t end = str.find(',', pos);
        if (end != std::string::npos)
        {
            GraphNode *node = new GraphNode(str.substr(pos, end - pos));
            node_vector.push_back(node);
        }
        else
        {
            break;
        }

        pos = str.find('#', pos);
        if (pos == std::string::npos)
        {
            break;
        }
        else
        {
            pos++;
        }
    }

    // add neighbors in every node
    for (size_t pos = 0; pos < str.length() - 1; )
    {
        GraphNode *current_node = NULL;
        size_t current_end = str.find(',', pos);
        if (current_end != std::string::npos)
        {
            current_node = get_one_node(node_vector, str.substr(pos, current_end - pos));
            pos = current_end + 1;
        }
        else
        {
            break;
        }

        size_t node_end = str.find('#', pos);   // 当前节点的字符串的结束位置
        if (node_end == std::string::npos)
        {
            node_end = str.length();
        }
        else
        {
            node_end--;
        }

        for ( ; ; )
        {
            current_end = str.find(',', pos);
            if (current_end > node_end || current_end == std::string::npos)
            {
                // 一个节点的最后一个邻接点
                current_end = node_end;
            }
            else 
            {
                current_end--;
            }

            GraphNode *node = get_one_node(node_vector, str.substr(pos, current_end - pos + 1)); 
            if (node != NULL)
            {
                current_node->neighbors.push_back(node);
                std::cout << current_node->label << " add " << node->label << std::endl;
            }
            if (current_end == node_end)
            {
                // 一个节点的最后一个邻接点
                break;
            }
            else
            {
                pos = current_end + 2;  // 该节点之后还有其他邻接点
            }
        }
        pos = node_end + 2;
    }
    return node_vector;
}

void DFS_traverse_recursion(GraphNode *node)
{
    if (!node->visited)
    {
        std::cout << node->label << '\t';
        node->visited = true;
    }
    for (std::vector<GraphNode *>::iterator iter = node->neighbors.begin(); iter != node->neighbors.end(); iter++)
    {
        if (!(*iter)->visited)
        {
            DFS_traverse_recursion(*iter);
        }
    }
}

/**
 * 图的深度优先搜索的递归形式
 */
void DFS_traverse_recursion(std::vector<GraphNode *> &graph)
{
    for (std::vector<GraphNode *>::iterator iter = graph.begin(); iter != graph.end(); iter++)
    {
        (*iter)->visited = false;
    }
    for (std::vector<GraphNode *>::iterator iter = graph.begin(); iter != graph.end(); iter++)
    {
        if (!(*iter)->visited)
            DFS_traverse_recursion(*iter);
    }
}

/**
 * 图的深度优先搜索的非递归形式
 */
void DFS_traverse_not_recursion(std::vector<GraphNode *> &graph)
{
    for (std::vector<GraphNode *>::iterator iter = graph.begin(); iter != graph.end(); iter++)
    {
        (*iter)->visited = false;
    }

    for (std::vector<GraphNode *>::iterator iter = graph.begin(); iter != graph.end(); iter++)
    {
        std::stack<GraphNode *> node_stack;
        if ((*iter)->visited)
        {
            continue;
        }
        node_stack.push(*iter);
        while (!node_stack.empty())
        {
            GraphNode *node = node_stack.top();
            node_stack.pop();
            if (node->visited)
                continue;
            std::cout << node->label << '\t';
            node->visited = true;
            /* 使用反向迭代器遍历后将节点加入到栈中 */
            for (std::vector<GraphNode *>::reverse_iterator iter2 = node->neighbors.rbegin(); iter2 != node->neighbors.rend(); iter2++)
            {
                if (!(*iter2)->visited)
                {
                    node_stack.push(*iter2);
                }
            }
        }
    }
}

/**
 * 图的广度优先搜索的非递归形式
 */
void BFS_traverse_not_recursion(std::vector<GraphNode *> &graph)
{
    for (std::vector<GraphNode *>::iterator iter = graph.begin(); iter != graph.end(); iter++)
    {
        (*iter)->visited = false;
    }

    for (std::vector<GraphNode *>::iterator iter = graph.begin(); iter != graph.end(); iter++)
    {
        std::queue<GraphNode *> node_queue;
        if ((*iter)->visited)
        {
            continue;
        }
        node_queue.push(*iter);
        while (!node_queue.empty())
        {
            GraphNode *node = node_queue.front();
            node_queue.pop();
            if (node->visited)
                continue;
            std::cout << node->label << '\t';
            node->visited = true;
            for (std::vector<GraphNode *>::iterator iter2 = node->neighbors.begin(); iter2 != node->neighbors.end(); iter2++)
            {
                if (!(*iter2)->visited)
                {
                    node_queue.push(*iter2);
                }
            }
        }
    }
}

/**
 * 二叉树的链式存储结构
 */
struct TreeNode
{
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(char data) : data(data), left(NULL), right(NULL) {}
};

/**
 * 构造二叉树，要构造的字符串采用了自顶向下、自左到右的顺序，跟leetcode的形式一致
 */
TreeNode *create_binary_tree(const char *str)
{
    if (!str || strlen(str) == 0)
    {
        return NULL;
    }

    // 对每个节点分配存储空间
    int node_size = strlen(str);
    TreeNode **tree = new TreeNode*[node_size];
    for (int i=0; i<node_size; i++)
    {
        if (str[i] == '#')
        {
            tree[i] = NULL;
        }
        else
        {
            tree[i] = new TreeNode(str[i]);
        }
    }

    for (int i=0, j=0; i<node_size && j<node_size; i++)
    {
        if (tree[i] != NULL)
        {
            if ((j + 1) < node_size)
            {
                tree[i]->left = tree[++j];
                tree[i]->right = tree[++j];
            }
        }
        else
        {
            j += 2;
        }
    }
    return *tree;
}

/**
 * 先序遍历的非递归形式
 */
void preorder_traverse_not_recursion(TreeNode *root)
{
    if (!root)
    {
        return ;
    }
    std::stack<TreeNode *> tree_stack;
    tree_stack.push(root);
    while (tree_stack.size() > 0)
    {
        TreeNode *node = tree_stack.top();
        tree_stack.pop();
        printf("%c\t", node->data);
        if (node->right != NULL)
        {
            tree_stack.push(node->right);   
        }
        if (node->left != NULL)
        {
            tree_stack.push(node->left);
        }
    }
}

/**
 * 中序遍历二叉树的递归形式
 */
void inorder_traverse_recursion(TreeNode *root)
{
    if (!root)
    {
        return;
    }
    
    inorder_traverse_recursion(root->left);
    
    printf("%c\t", root->data);

    inorder_traverse_recursion(root->right);
}

/**
 * 中序遍历二叉树的非递归形式
 */
void inorder_traverse_not_recursion(TreeNode *root)
{
    if (!root)
    {
        return ;
    }
    std::stack<TreeNode *> tree_stack;
    while (root != NULL || tree_stack.size() > 0)
    {
        // 遍历到左子树的叶子节点
        while (root)
        {
            tree_stack.push(root);
            root = root->left;
        }

        // 遍历栈顶节点
        root = tree_stack.top();
        tree_stack.pop();
        printf("%c\t", root->data);

        root = root->right;
    }
}

/**
 * 后序遍历二叉树的递归形式
 */
void postorder_traverse_recursion(TreeNode *root)
{
    if (!root)
    {
        return;
    }
    
    postorder_traverse_recursion(root->left);
    
    postorder_traverse_recursion(root->right);

    printf("%c\t", root->data);
}

/**
 * 后序遍历二叉树的非递归形式
 */
void postorder_traverse_not_recursion(TreeNode *root)
{
    if (!root)
    {
        return ;
    }
    std::stack<TreeNode *> tree_stack;
    TreeNode *visited = NULL;
    while (root != NULL || tree_stack.size() > 0)
    {
        // 遍历到左子树的叶子节点
        while (root)
        {
            tree_stack.push(root);
            root = root->left;
        }

        root = tree_stack.top();

        if (root->right == NULL || root->right == visited)
        {
            // 如果没有右孩子，或者右孩子刚刚访问过，则访问当前节点
            printf("%c\t", root->data);
            tree_stack.pop();
            visited = root;
            root = NULL;
        }
        else
        {
            root = root->right;
        }
    }
}