用字符串创建二叉树。例如：1,2,3,#,#,4,5,#,#,#,#,

Question

我正在使用 BFS 算法从字符串中创建一个二叉树，我有一个问题：为什么我要在while循环后写“TreeNode node = tree.front();”而不是“根=tree.front();”。为什么我不能只使用已经创建的 TreeNode root ?

TreeNode* helper(queue<string> &q) {
    string data = q.front(); q.pop();
    if (data == "#") return NULL;
    
    queue<TreeNode*> tree;
    TreeNode* root = new TreeNode(stoi(data));
    tree.push(root);

    while(!tree.empty()) {
        int size = tree.size();
        for (int i = 0; i < size; i++) {
            TreeNode* node = tree.front();

            string newNode = q.front(); q.pop();
            if (newNode != "#") {
                node -> left = new TreeNode(stoi(newNode));
                tree.push(node -> left);
            } 

            string newNode = q.front(); q.pop();
            if (newNode != "#") {
                node -> right = new TreeNode(stoi(newNode));
                tree.push(node -> right);
            }

            tree.pop();
        }
    }
    return root;
}

Answer 1

因为root指向树的根，这就是函数应该return，而树的根已经确定了（它是输入的第一个元素排队）。

写root = tree.front()会使最后创建的节点成为树的根节点，树将只有一个元素。

用字符串创建二叉树。例如：1,2,3,#,#,4,5,#,#,#,#,

Creating a binary tree out of string. Ex: 1,2,3,#,#,4,5,#,#,#,#,

c++

binary-tree

pointers

breadth-first-search

data-structures