二叉树 - 查找节点数k深度-Java 学习之路

以下函数在二叉树上运行 . 该函数将获取指向树根的指针和非负int k . 它应该从根返回节点k深度的数量 .

struct treenode {
  int data;
  struct treenode* left;
  struct treenode* right;
}

int numNodesHeightK(struct treenode* root, int k){
  if(root == NULL) return 0; //if the tree is empty return 0
  if(k == 0) return 1; //if k = 0, then the root is the only node to return 

  //How does this statement work?
  return numNodesHeightK(root->left, k-1) + numNodesHeightK(root->right, k-1);
}

如果有人能够解释最终陈述的逻辑 . 我没有看到这行代码如何返回正确的深度 .

5 回答

3

对于每个节点，您希望将每个子树的深度为 k 的节点数加在一起 . 这意味着从各自的根（当前节点的左右子树）遍历那些深度为 k-1 的节点的子树 . 当 k 到达 0 时，这意味着为该节点返回 1 ，因为它是来自原始根的深度 k .

最后一个语句完全执行此操作 - 首先遍历左子树，然后遍历右子树，从当前节点查找深度为 k 的节点数，将它们相加，然后返回结果 .

该算法非常简单 - 在纸上绘制测试树并逐步完成 . 逻辑应该很快跳出来 .

回复于 2024-05-03T20:50:12+08:00
0
该理论是给定深度处的节点总数（假设深度= 5）与从左子节点和右子节点计数的深度= 4的节点的总和相同 . （因为搬到孩子身上已经引入了1的深度） .

所以，让我们在左子上找到深度为4的节点数：
```
numNodesHeightK(root->left, k-1)
```
右子上的深度为4的节点数：
```
numNodesHeightK(root->right, k-1)
```
并将它们添加到一起以获得从当前节点获取深度5的节点数的答案 .

直到你要求深度0处的节点数量（这显然为1）时，这一点才能完全解决 . 这是在函数的基本情况下实现的：
```
if(k == 0) return 1; //if k = 0, then the root is the only node to return
```
最后，你可以互换使用“高度”和“深度”这两个术语，如果你试着谈论“向下”或“向上”树，这会让人感到困惑 . 选择一个约定并坚持下去 .
回复于 2024-05-03T20:50:12+08:00
1
只是递归地想一想......

一个子树中有多少个节点，其中的roor是 null ？ 0
```
if (root == NULL) return 0;
```
在深度为0的节点下有多少个节点？ 1 （节点本身） .
```
if (k == 0) return 1;
```
否则有多少个节点和子节点有一棵树？左侧分支上的节点加上右侧分支上的节点 . 每个分支都处于较低级别 .
```
// left side
numNodesHeightK(root->left, k-1) +
// right side 
numNodesHeightK(root->right, k-1)
```
回复于 2024-05-03T20:50:12+08:00
0

画一幅如何运作的画面......

想想你有这个团队执行任务，并且有这些隧道继续分叉两个子通道 . 我们的目标是找出这么多的叉子，这些叉子可以通向一个洞穴 . 货叉之间的距离是一个长度单位 .

每当你到达隧道中的一个分支时，该分支的当前组将分成两半，并将每一半分别发送到两个子通道 .

每当小组分开K次时，他们就会停下来看看这个位置 . 然后他们回到水面，每个人都告诉他是否找到距离入口k的房间 . 如果任何子团队在距离k之前到达死胡同，他们会返回并说没有空间 .

他们将总数加起来并向您汇报 .

房间是节点 . 分叉是每个节点的子节点 . 子团队是您的方法在堆栈上的调用 .

回复于 2024-05-03T20:50:12+08:00
1

单独理解一行是不可能的，因为函数是递归的，并且一行是递归的行 .

但是只有三行，所以我们可以很容易地了解整个事物 .

为了计算给定深度处的节点，有必要将树遍历到该深度 .

这意味着我们递归地采用每个左右分支 .

前两条可执行行

如果我们从叶节点向下遍历到空节点，我们只返回0.如果我们发现自己处于正确的深度，我们可以阻止任何无意义的遍历在树中并返回1，因为我们的递归函数的实例已经落在目标深度的单个节点上 . 这条线阻止我们不必要地穿越，以及为我们所在的分支提供计数 .

最后一行

最后，你的最后一行 . 在每个更浅的层次上，有必要深入到树中，并且在递归实现中通过为树的每个分支调用函数的新实例来完成 . 该行可以再次执行调用实例，直到调用图本身累积镜像实际树，并且每个级别返回越来越大的合并总和到先前的级别，最终从顶级节点的单个实例返回单个可能相当大的数字 .

回复于 2024-05-03T20:50:12+08:00

二叉树 - 查找节点数k深度

5 回答

前两条可执行行

最后一行

相关问题