二叉树--求k深度的节点数 [英] Binary Tree -- Finding the number of nodes k depth

问题描述

以下函数对二叉树进行操作。该函数将接受指向树根的指针和非负的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);
}

如果有人能解释一下最后陈述的逻辑。我不明白这行代码如何返回正确的深度。

推荐答案

对于每个节点，您需要将每个子树中深度k的节点数相加。这意味着要遍历这些子树，寻找从它们各自的根(当前节点的左子树和右子树)开始深度k-1的节点。当k到达0时，这意味着返回该节点的1，因为它是从原始根开始的深度k。

最后一条语句执行的正是这个操作--首先遍历左子树，然后遍历右子树，从当前节点找到深度k的节点数，将它们相加，然后返回结果。

该算法非常简单--在纸上绘制一棵测试树，然后逐步完成它。你应该很快就会明白其中的逻辑。

这篇关于二叉树--求k深度的节点数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！