java - 用从根到叶子的路径之和改变树的叶子的值

Question

我必须创建一个函数，使树不为空，通过将包含在从根到叶的路径的节点中的值的总和(包括根和叶)。

所以我创建了这个:

void sum(BinTree t) {
    while(!t.isLeaf()) {
        sumL += sum(t.left);
        sumR += sum(t.right);
    }
    t.element = ?;
}

boolean isLeaf(BinTree t) {
    return t.left == null && t.right == null;
}

我应该用什么代替“？”？我不认为这个功能是正确的.. 我无法为二叉树创建递归函数，我发现它们非常复杂..

谢谢

---

编辑:我改变了我的方法:

void leafSum(BinTree t) {
    sumLeaf(root, 0);
}

void leafSum(BinTree t, int tot) {
    if(t->left == NULL && t->right == NULL)
        t->elem = tot;
    else {
        sumLeaf(t->left, tot + t->elem);
        sumLeaf(t->right, tot + t->elem);
    }
}

Answer 1

我不会提供解决方案，而是提供一些提示来帮助您。如果有任何不清楚的地方，请提出问题。

• 您正在寻找的基本算法是:对于每个节点，如果它是叶子，则存储总和，如果它不是叶子，则对两个子节点重复。

• 虽然递归不是必需的，但在这种情况下它会使解决方案更简单。这并不复杂:基本规则是在递归之前始终有一个终止条件(在您的情况下，您正在查看一片叶子)。

• 您应该将运行总计传递给该函数，这样您就不需要在到达叶节点后回头查看树。这并不复杂:只需将节点的当前值添加到运行总计中，然后再将其存储(对于叶子)或将其传递给子节点(对于非叶子)。

• 当您为根节点调用函数时，从零开始运行。

仅此而已 - 您应该能够从这些提示中找到解决方案。