java - 难以理解递归算法中的最终调用返回什么，提供了算法示例

Question

所以我有一个面试时给我的伪代码算法，它遍历二叉树并返回某种值。在用绘制的二叉树跟踪算法之后，我不断地猜测自己，当算法返回到根时，我是否在最终调用中返回 2 + valOne + valTwo ，或不。当我应用该方法时，根据我的计算，返回的数字是 2*(树的高度)，我想检查我的答案和逻辑是否正确。根据练习表的答案声称它计算树中的边数，但我完全不明白这是怎么可能的。

public int foo(r){
         if(r is leaf) return 0;
         else{
             valOne = foo(r.leftChild());
             valTwo = foo(r.rightChild());
             return 2 + valOne + valTwo;
         }

那么 return 2 + valOne + valTwo 是否也应用于整个树的根？如果是的话，我的答案是否不正确？谢谢大家!

Answer 1

对于每个非叶节点都有左子节点和右子节点的二叉树，这会计算边的数量。

valOne = foo(r.leftChild()); // count edges in left subtree

valTwo = foo(r.rightChild()); //count edges in right subtree

return 2 + valOne + valTwo; // 2  (the edges from this node to its children) + edges in sub trees

if(r is leaf) return 0; //leaf nodes have no edges pointing out