时间戳

首页 > 解决方案 > 无法理解递归算法中的最终调用返回什么，提供了算法示例

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

问题描述

所以我有这个伪代码算法，我接受了一次采访，它遍历二叉树并返回某种值。在用绘制的二叉树跟踪算法之后，我不断猜测自己是否2 + valOne + valTwo在算法返回到 root 时返回最终调用。当我应用它时，根据我的计算返回的数字是 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也适用于整个树的根？如果是的话，我的回答会不正确吗？感谢你们！

标签： javarecursion

解决方案

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

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

推荐阅读