树的逐级求和？

Question

这肯定是一个老掉牙的问题了，但我没找到满意的答案。假设一颗树，原来只有叶节点包含数值，如下面的节点N111，N112，N121和N21。
[code]ROOT
  |-- N1
    |-- N11
      |-- N111(30)
      |-- N112(10)
    |-- N12
      |-- N121(10)
  |-- N2
    |-- N21(30)[/code]
现在要逐级地把下级节点中的数值累加到它们父节点中，直至根节点，即最终的结果如下所示，
[code]ROOT(80)
  |-- N1(50)
    |-- N11(40)
      |-- N111(30)
      |-- N112(10)
    |-- N12(10)
      |-- N121(10)
  |-- N2(30)
    |-- N21(30)[/code]
目前我使用递归算法解决上述问题，但希望能够使用迭代算法，可不清楚如何进行转换:(

Answer 1

这肯定是一个老掉牙的问题了，但我没找到满意的答案。假设一颗树，原来只有叶节点包含数值，如下面的节点N111，N112，N121和N21。
ROOT
  |-- N1
    |-- N11
      |-- N111(30)
      |-- N112(10)
    |-- N12
      |-- N121(10)
  |-- N2
    |-- N21(30)
现在要逐级地把下级节点中的数值累加到它们父节点中，直至根节点，即最终的结果如下所示，
ROOT(80)
  |-- N1(50)
    |-- N11(40)
      |-- N111(30)
      |-- N112(10)
    |-- N12(10)
      |-- N121(10)
  |-- N2(30)
    |-- N21(30)
目前我使用递归算法解决上述问题，但希望能够使用迭代算法，可不清楚如何进行转换:(

Answer 2

//树节点的定义
public class TreeNode {
public TreeNode(int value, TreeNode left, TreeNode right) {
this.value = value;
this.left = left;
this.right = right;
}
public int value;
public TreeNode left;
public TreeNode right;
}
//可以直接运行的例子
import java.util.Stack;public class Main { /**
 * @param args
 */
public static void main(String[] args) {
new Main().go();
} public void go() {
TreeNode tree = initTree();
doLevelSum(tree);
System.out.println(tree.value);
}

//根据楼主的例子，初始化一棵树
public TreeNode initTree() {
TreeNode n111 = new TreeNode(30, null, null);
TreeNode n112 = new TreeNode(10, null, null);
TreeNode n11 = new TreeNode(0, n111, n112);
TreeNode n121 = new TreeNode(10, null, null);
TreeNode n12 = new TreeNode(0, n121, null);
TreeNode n1 = new TreeNode(0, n11, n12);
TreeNode n21 = new TreeNode(30, null, null);
TreeNode n2 = new TreeNode(0, n21, null);
TreeNode root = new TreeNode(0, n1, n2);
return root;
}

//逐级求和，用迭代
public void doLevelSum(TreeNode tree) {
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(tree);
TreeNode node;
int a, b;
while(!stack.empty()) {
node = stack.peek();
if((node.left != null && node.left.value==0) || (node.right != null && node.right.value==0)) {
if(node.left != null && node.left.value==0)
stack.push(node.left);
if(node.right != null && node.right.value==0)
stack.push(node.right);
}else {
a = b = 0;
if(node.left != null)
a = node.left.value;
if(node.right != null)
b = node.right.value;
node.value = a + b;
stack.pop();
} }
}
}

Answer 3

非常感谢andycpp的帮助，结帖时肯定奖分 ^_^不过，我的树并不是二叉树，每个节点可以有任何数量的子节点。
我的树节点定义类似于
TreeNode {
 
  private TreeNode parent = null;
 
  private List<TreeNode> children = new ArrayList<TreeNode>(); // 可以有任意数量的子节点。  private Object value = null;  ...
}

Answer 4

答:用栈就行了.但比二叉树明显复杂,不是很简单的. 对于任意的树,伪代码如下:[已手工测试过,正确]说明:栈中元素是三元组(node,lv,flag)
node--结点
lv--该结点左边的兄弟们结点值之和
flag: false--表示准备通过儿子们结点来求值
       true--表示已经可以求出该结点值了
public void treeSum(TreeNode r)
{
 int ss=0;//目前为止,儿子们结点值之和
 if(r==null||r是叶子)return;
 将树根r结点的三元组(r,0,true)进栈.[注意是:true]
 将树根r的所有的儿子们结点从右向左依次进栈,三元组是(son,0,false)[注意是:false]
 while(栈不空)
 {
  出栈=>三元组(node,lv,flag);
  if(node是叶子){ss=ss+node.value;continue;}
  //此时:node肯定不是叶子了
  if(flag==false)//必须要通过儿子们来求值
  {
  将node再次进栈,三元组是(node,ss,true);
  将node的所有的儿子们结点从右向左依次进栈,三元组是(son,0,false)[注意是:false]
  ss=0;//开始计算node的儿子们值之和
  }
  else 
  {//表示儿子们之和已求出.放在ss中,可以对结点求值了
   node.value=ss;
   ss=ss+lv;//将node的儿子们之和 加上 node的兄弟们之和,作为新的node的父结点的目前的儿子们的和
  }//if
 }//while
}