寻找子树中值小于自身节点的最大数量

原文链接: https://www.geeksforgeeks.org/find-the-node-whose-subtree-has-maximum-number-of-nodes-which-are-greater-than-the-node-itself/

问题描述：给定一棵二叉树，需要找出一个节点，该节点的子树中包含最大数量的值小于该节点的节点。如果有多个节点满足条件且拥有相同数量的小于自身的节点，则可以返回其中任何一个。

示例:

输入:

4
/\
6 10
/\/\
2 3 7 14
/
5

输出: 6
解释: 值为 6 的节点的子树中有 3 个节点（2，3，5）的值小于 6，这是所有节点中最多的。

输入:
10
21
2 411

输出: 21
解释: 值为 21 的节点的子树中有 3 个节点（2，4，11）的值小于 21，这是所有节点中最多的。

解决方案: 可以通过后序遍历来解决这个问题。具体步骤如下：

1. 对给定的树执行后序遍历。
2. 对于每个节点，检查其左子树和右子树中的节点值是否小于当前节点的值，并记录这些节点的数量。
3. 递归地应用上述步骤到每个节点，计算每个节点的子树中小于当前节点的节点数量。
4. 在遍历完成后，选择并返回具有最大小于自身节点数量的节点。

以下是该方法的实现代码：

C++ 实现

// C++ 程序实现
#include
using namespace std;
unordered_map mp;
struct Node {
int key;
Node *left, *right;
};
Node* newNode(int key) {
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = nullptr;
return temp;
}
vector findNodes(Node* root, int& max_count, int& result) {
if (!root) return {};
vector left = findNodes(root->left, max_count, result);
vector right = findNodes(root->right, max_count, result);
vector combined = {root->key};
int count = 0;
for (int val : left) {
if (val key) ++count;
combined.push_back(val);
}
for (int val : right) {
if (val key) ++count;
combined.push_back(val);
}
if (count > max_count) {
max_count = count;
result = root->key;
}
return combined;
}
int main() {
Node* root = newNode(3);
root->left = newNode(4);
root->right = newNode(6);
root->right->left = newNode(4);
root->right->right = newNode(5);
root->left->left = newNode(10);
root->left->right = newNode(2);
int max_count = 0, result = -1;
findNodes(root, max_count, result);
cout <}

输出: 6

时间复杂度: O(N^2)
空间复杂度: O(N)