该方法如何添加所有BST节点的大小？

我不明白sum是如何递增的，因为每次调用该方法时它被重置为1。我知道内存被存储在一个堆栈中，但我看不到实际的总和发生在哪里。当变量和在方法内部而不是在方法外部声明时，也会节省多少内存。该方法如何添加所有BST节点的大小？

private int size(BSTNode current) { 
     if (current == null) { 
      return 0; 
     } 
    int sum = 1; 
    sum += size(current.getLeft()); 
    sum += size(current.getRight()); 
    return sum; 
    }

来源

2016-09-22 Zachary Cheshire

假设你加入成为公司的一个部门的负责人，想知道是谁在该部门工作的总人数。此外，还有2名负责人，一名负责工程，另一名负责业务。现在，为了统计人数，你可以到办公室去计数。（但是这很乏味，除此之外，作为部门负责人有什么意义）。

或者，你可以做的是要求你的工程负责人找出在他下面工作的人，说x，并要求业务负责人找出在他下面工作的人，说y。所以，在该部门工作的人员总数是x+y+1（1是给你的）。

现在，您可以假设工程负责人将拥有2名主管，并要求他们了解每位主管正在监督的人数。因此，工程团队的总人数为people_under_supervisor_1 + people_under_supervisor_2 + 1（工程负责人为1人）。等等。

同样，您可以假设一个类似的流程，涉及通过业务负责人查找业务部门中的人员数量。

这代码做同样的事情，找到左子树的大小，发现右子树的大小，加1为当前节点。这是算法的工作原理。我希望这个比喻有帮助。

现在，关于“多少更多的内存保存在变量和方法内声明的而不是方法之外。” 其实当你在声明一个局部变量更多的内存使用递归函数。在声明任何局部变量时，将在堆栈中分配一个内存位置，并且该局部变量的作用域完成之前，该内存位置不能用于其他目的。因此，当下一个函数被称为size(current.getLeft())时，所有变量都保留在堆栈中，并且通过调用size(current.getLeft())创建局部变量size的新内存位置。只要该函数仍未返回结果，size的实例就保留在内存中。

看看这个视频，https://www.youtube.com/watch?v=_8-ht2AKyH4得到一个更清晰的堆栈的想法。

来源

2016-09-22 22:21:12

你的代码做：

int sum = 1;      // +1 for current node 
sum += size(current.getLeft()); // +size of leftSubtree of current node 
sum += size(current.getRight()); // +size of rightSubtree of current node

您是从根开始，下到每一个节点，直到叶节点，然后从底部恢复回来，因为它上升，+1是为每一个做节点。

变量名称sum的使用在实际您尝试计算节点数时会引入误导。使用名称如count或node_count

来源

2016-09-23 01:47:26

该方法如何添加所有BST节点的大小？

回答

相关问题