具有最多M个连续节点且值为K的从根到叶子的路径数量

简介

二叉树是一种令人着迷的数据结构，在计算机科学和编程中有着广泛的应用。一个有趣的问题是从给定的由父节点及其子节点组成的树中查找计数。二叉树由节点组成，根节点确定，根节点可以根据用户需要给出子节点。 K值决定，移动方式由M值选择。

根到叶路径的计数

该图是使用各种节点创建的，这些节点保存整数形式的值。本文主要关注从起始节点或根节点到叶子节点或子节点的计数。

示例

该图是从具有各种节点的二叉树创建的。

• 在上面的二叉树中，根节点选择为“8”。

• 然后创建两个节点，一个值为 3，另一个值为 10，占据根节点的左右位置。

• 以值为 2 的节点作为根，创建另一个子节点，其值分别为 2 和 1 作为左节点和右节点。

• 最后，值为 1 的子节点创建值为 -4 的子节点。

方法 1：使用递归函数计算由最多 M 个具有 K 值的连续节点组成的根到叶路径的 C++ 代码

为了有效地解决这个问题，我们将利用树遍历算法和递归等基本概念。

算法

第 1 步：创建一个用于表示树节点的结构，其中包括两个指针（左子节点和右子节点）以及用于存储节点值的整数字段。

第 2 步：设计一个递归函数，从根开始遍历二叉树，同时跟踪当前路径长度（初始化为 0）、连续出现次数（初始设置为 0）、目标值 K，允许的最大连续出现次数 M。

第 3 步：在每个左子树和右子树上递归调用该函数，并传递更新的参数，例如递增的路径长度和连续出现次数（如果适用）。

第4步：对于遍历过程中每个访问过的非空节点：

a) 如果其值等于 K，则将两个变量都加一。

b) 如果其值与 K 不匹配或超过迄今为止在路径中已遇到的 M 连续出现次数，则将变量重置为零。

第5步：在遍历树时，如果子节点在左和右两种情况下的值都为零 - 我们可以用两种方式处理，即

a) 检查变量是否不超过M。

b) 如果是，则将满足条件的路径总数增加 1。

示例

//including the all in one header
#include<bits/stdc++.h>
using namespace std;
//creating structure with two pointers as up and down
struct Vertex {
   int data;
   struct Vertex* up;
   struct Vertex* down;
};
//countPaths function declared with five arguments ; with root = end; Node= vertex; left = up; right = down
int countPaths(Vertex* end, int K, int M, int currCount, int 
consCount) {
//To check the condition when the root is equal to 1 and greater than the maximum value, the values is incremented
   if (end == NULL || consCount > M) {
      return 0;
   }
//To check when the root is equal to the K value, increment by 1
   if (end->data == K) {
      currCount++;
      consCount++;
   } else {
//If it is not equal, it will return 0
      currCount = 0;
   }
   if (end->up == NULL && end->down == NULL) {
      if (currCount <= M) {
         return 1;
      } else {
         return 0;
      }
   }
   return countPaths(end->up, K, M, currCount, consCount) + countPaths(end->down, K, M, currCount, consCount);
}
//Main function to test the implementation
int main() {
   Vertex* end = new Vertex();
   end->data = 8;
   end->up = new Vertex();
   end->up->data = 3;
   end->down = new Vertex();
   end->down->data = 10;
   end->up->up = new Vertex();
   end->up->up->data = 2;
   end->up->down = new Vertex();
   end->up->down->data = 1;
   end->up->down->up = new Vertex();
   end->up->down->up->data = -4;

   int K = 1; // Value of node
   int M = 2; // Maximum consecutive nodes
   int currCount = -1; // Current count
   int consCount = -1; // Consecutive count

   cout << "The number of paths obtained from the given graph of" << M << "nodes with a value of " << K << " is " << countPaths(end, K, M, currCount, consCount) << endl;

   return 0;
} 

输出

The number of paths obtained from the given graph of 2 nodes with a value of 1 is 3

结论

在本文中，我们探讨了计算从顶部（即叶）到末端或根的路径数的问题。通过使用 C++ 中的树遍历算法和递归技术，可以有效地解决此类问题。遍历二叉树的过程看起来很困难，但通过示例就变得简单了。

以上是具有最多M个连续节点且值为K的从根到叶子的路径数量的详细内容。更多信息请关注PHP中文网其他相关文章！