使用从根到叶的路径总和来更改树的叶子的值

我必须创建一个使树不为空的函数，通过将树中的每个叶子的内容包含在从根到叶的路径（包括根和叶）的节点中的值。使用从根到叶的路径总和来更改树的叶子的值

所以我创造了这个：

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; 
}

我应该把什么代替 “？”？我不认为该函数是正确的.. 我无法为二叉树创建递归函数，我觉得他们很复杂..

感谢

编辑：我changhed我方法：

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); 
    } 
}

来源

2015-06-01 user4963215

对不起，听起来很刺耳，但这意味着你需要尝试更多，并学习更多。你将如何执行这项任务？ –

查看这篇有关树遍历的wiki文章：http://rosettacode.org/wiki/Tree_traversal#Java Java中有一些例子可以复制和粘贴，只需要修改数学。是的，所有的例子都是递归的。虽然可以遍历一个没有递归的树，但它被广泛认为是一个丑陋的解决方案。 –

与其提供解决方案，我会提供一些提示以帮助您一起。如有任何不清楚的地方，请提出问题。

你正在寻找的基本算法是：对于每一个节点，如果它是一个叶子，然后储存总和，如果它不是叶然后重复两个子节点。
虽然递归并不是必需的，但在这种情况下会使解决方案更简单。这并不复杂：基本规则是在递归之前总是有终止条件（在你的情况下，你正在查看叶子）。
您应该将一个运行总数传递给该函数，以便您在进入树叶后不需要回看树。这并不复杂：只需在将节点的当前值添加到运行总计中（对于叶节点）或将其传递给子节点（对于非叶节点）即可。
当您调用根节点的函数时，以总计零的运行开始。

就是这样 - 你应该能够从这些提示中提出解决方案。

来源

2015-06-02 00:02:50 sprinter

使用从根到叶的路径总和来更改树的叶子的值

回答

相关问题