二叉树中高度为h的子树

Question

如何在二叉树中找到高度为"h"的子树的数量。函数定义为int子树(node*root，int k(；其中k是特定高度。

Answer 1

首先，我们递归计算树的高度，如下所示：

如果树为空，则高度为0。

如果树不是空的，则高度是其子树的最大高度加1。

在C中(我假设OP根据响应使用C(，这看起来像

typedef struct Node {
Node* leftChild,
node* rightChild
} Node;
typedef Node* Tree;
unsigned int max(unsigned int a, unsigned int b) {
return a > b ? a : b;
}
unsigned int height(Tree tree) {
return tree ? 1 + max(height(tree->leftChild, tree->rightChild)) : 0;
}

请注意，Node通常会有一些额外的数据。但这些数据在这里并不相关，所以我们不包括它(尽管如果你愿意，这样做很容易(。

现在，我们想稍微修改一下height函数。为此，我们定义

typdef struct Result {
unsigned int height,
unsigned int count
} Result;
/**
* The returned .height should be the height of the tree.
* The returned .count should be the number of subtrees of tree
* with height k.
*/
Result resultCountChildren(Tree tree, unsigned int k) {
if (tree) {
Result leftResult = resultCountChildren(tree->left, k);
Result rightResult = resultCountChildren(tree->right, k);
unsigned int heightOfTree = 1 + max(leftResult.height, rightResult.height);
unsigned int count = leftResult.count + rightResult.count + (heightOfTree == k);
Result result = {
.height = heightOfTree,
.count = count
};
return result;
} else {
unsigned int height = 0;
unsigned int count = (0 == k);
Result result = {
.height = height,
.count = count
};
return result;
}
}
unsigned int count(Tree tree, unsigned int k) {
return resultCountChildren(tree).count;
}