@dc65k

Как решить задачу с обходом дерева с помощью цикла?

Все привет. Подскажите, как решить задачу с обходом дерева с помощью цикла?
Есть пример задачи:
const tree = [
    {
        v: 5,
        c: [
            {
                v: 5
            },
            {
                v: 10,
                c: [
                    {
                        v: 11,
                    }
                ]
            },
            {
                v: 11,
                c: [
                    {
                        v: 12,
                        c: [
                            {
                                v: 5
                            }
                        ]
                    }
                ]
            },
        ]
    },
    {
        v: 5,
        c: [
            {
                v: 7
            },
            {
                v: 12,
                c: [
                    {
                        v: 11,
                    }
                ]
            },
            {
                v: 14,
            },
        ]
    }
]

function treeSum(tree) {

    if (!tree.length) {
        return 0;
    }

    let sum = 0;

    let stack = [];

    tree.forEach(node => stack.push(node));

    console.log(tree);

    while (stack.length) {
        let node = stack.pop();

        sum += node.v;

        if (node.c) {
            node.c.forEach(node => stack.push(node));
        }
    }

    return sum;
}

treeSum(tree);

Задача выше решена. И, к примеру, есть схожая структура данных:
const binaryTree = {
    value: 1,
    left: {
        value: 2,
        left: {
            value: 3,
            left: {
                value: 4
            }
        },
        right: {
            value: 5
        }
    },
    right: {
        value: 6,
        left: {
            value: 7
        },
        right: {
            value: 8
        }
    }
}


Следуя тому же подходу, очевидно, где-то неправильно.
function treeSum2(tree) {
    let stack = [];

    const output = [];

    Object.keys(tree).forEach(node => {
        stack.push(tree[node]);
    });

    while (stack.length) {
        let node = stack.pop();

        output.push(node.value);

        /*
        if (node.left) {
            Object.keys(node.left).forEach(node => {
                stack.push(node);
            });
        }

        if (node.right) {
            Object.keys(node.right).forEach(node => {
                stack.push(node);
            });
        }

        */
    }

    return output;
}

treeSum2(binaryTree);
  • Вопрос задан
  • 102 просмотра
Решения вопроса 1
Alexandroppolus
@Alexandroppolus
кодир
function treeSum2(tree) {
    const stack = [tree];
    let result = 0;
    while (stack.length) {
        const item = stack.pop();
        if (item) {
            result += item.value;
            stack.push(item.left);
            stack.push(item.right);
        }
    }
    return result;
}
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы