数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++移除长度小于K的根到叶路径上的节点
给定一棵树，我们需要移除路径长度小于给定值k的叶子节点，例如：
输入 -
K = 4.
输出 -
解释
The paths were : 1. A -> B -> C -> E length = 4 2. A -> B -> C -> F length = 4 3. A -> B -> D length = 3 4. A -> G -> H length = 3 5. A -> B -> I length = 3 Now as you can see paths 3, 4, 5 have length of 3 which is less than given k so we remove the leaf nodes of these paths i.e. D, H, I. Now for path 4 and 5 when H and I are removed we notice that now G is also a leaf node with path length 2 so we again remove node G and here our program ends.
我们将使用后序遍历方式遍历树；然后，我们创建一个递归函数，如果叶子节点的路径长度小于K，则移除该节点。
解决方案方法
在这种方法中，我们使用后序遍历；我们尝试递归地移除路径长度小于k的叶子节点，以此类推。
示例
上述方法的C++代码
#include<bits/stdc++.h>
using namespace std;
struct Node{ // structure of our node
char data;
Node *left, *right;
};
Node *newNode(int data){ // inserting new node
Node *node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
Node *trimmer(Node *root, int len, int k){
if (!root) // if root == NULL then we return
return NULL;
root -> left = trimmer(root -> left, len + 1, k); // traversing the left phase
root -> right = trimmer(root -> right, len + 1, k); // traversing the right phase
if (!root -> left && !root -> right && len < k){
delete root;
return NULL;
}
return root;
}
Node *trim(Node *root, int k){
return trimmer(root, 1, k);
}
void printInorder(Node *root){
if (root){
printInorder(root->left);
cout << root->data << " ";
printInorder(root->right);
}
}
int main(){
int k = 4;
Node *root = newNode('A');
root->left = newNode('B');
root->right = newNode('G');
root->left->left = newNode('C');
root->left->right = newNode('D');
root->left->left->left = newNode('E');
root->left->left->right = newNode('F');
root->right->left = newNode('H');
root->right->right = newNode('I');
printInorder(root);
cout << "\n";
root = trim(root, k);
printInorder(root);
return 0;
}输出
E C F B D A H G I E C F B A
上述代码的解释
在这个代码中，我们使用一个递归函数来遍历树并保持左右子树的状态。当我们到达叶子节点时，我们检查到该节点的路径长度。如果路径长度小于k，则删除该节点并返回NULL；否则，代码继续执行。
结论
在本教程中，我们解决了一个问题：使用递归移除长度小于K的根到叶路径上的节点。我们还学习了这个问题的C++程序和递归以及我们解决的完整方法。我们可以用其他语言（如C、Java、Python等）编写相同的程序。希望本教程对您有所帮助。
更新于：2021年11月26日
浏览量：117
广告