在给定总和K的二叉树中找到级别

Description:

描述：

The article describes how to find the level in a binary tree with given sum K? This is an interview coding problem came in Samsung, Microsoft.

本文介绍了如何在给定总和K下在二叉树中找到级别 ？ 这是一个面试编码问题，来自三星，微软。

Problem statement:

问题陈述：

Given a binary tree and an integer K, output the level no of the tree which sums to K. Assume root level is level 0.

给定一棵二叉树和一个整数K ，输出该树的级数之和为K。 假设根级别为0 。

Solution

解

Algorithm:

算法：

One of the popular traversal techniques to solve this kind of problems is level order tree traversal (Read more: Level Order Traversal on a Binary Tree) where we use the concept of BFS with some modifications.

解决此类问题的一种流行的遍历技术是级别顺序树遍历(更多内容： 二叉树上的级别顺序遍历 )，其中我们使用了经过修改的BFS概念。

1. Set a variable level=0 & declare a variable of type tree* named temp. level is a flag for the current level & temp stores tree node to be processed.

1.设置变量level = 0并声明一个名为temp的 tree *类型的变量。 级别是当前级别和临时存储要处理的树节点的标志。

2. Set cur_sum=0

2.设置cur_sum = 0

3. if(!root) // root is NULL
return -1; //no such level exists

3. if(！root) //根为NULL
返回-1; //不存在这样的级别

4. q=createQueue() //to store pointers to tree node

4. q = createQueue() //存储指向树节点的指针

5. EnQueue(q,root);

5. EnQueue(q，root);

6. EnQueue(q,NULL);

6. EnQueue(q，NULL);

Every time, we EnQueue a NULL to reflect the end of current level. Same way while processing when NULL is found, it reveals that end of current level.

每次，我们将NULL排队以反映当前级别的结束。 发现NULL时进行处理的方式相同，它显示当前级别的末尾。

7. while( q is not empty)temp=DeQueue(q);if(temp==NULL){ //end of current levelif (cur_sum==K) // current level sum is equal to KReturn level; //return level no (root is at 0 level)else {Set cur_sum =0; // for next levelIf(q is not empty)// to reflect end of next level which // will be processed in next iterationEnQueue(q,NULL)Increase level //increase level count}}Else{cur_sum+=temp->data; //sum the level//do level order traversalIf(temp->left)EnQueue(temp->left);If(temp->right)EnQueue (temp->right);} End while loop

8. If program control comes out of while loop then surely no level has a sum K. Thus print no level has sum K

8.如果程序控制从while循环中出来，那么肯定没有水平的总和为K。 因此打印无级别的总和为K

Example:

例：

Here the level sums are: For level 0: 2 For level 1: 12 For level 2: 17 For level 3: 20 Thus if K is 12 our program will print level 1 .minHeight{min-height: 250px;}@media (min-width: 1025px){.minHeight{min-height: 90px;}} .minHeight{min-height: 250px;}@media (min-width: 1025px){.minHeight{min-height: 90px;}}

C ++代码在给定总和为K的二叉树中找到级别 (C++ code to find the level in a binary tree with given sum K)

#include <bits/stdc++.h> using namespace std;// tree node is defined class tree{public:int data;tree *left;tree *right; };int findLevel( tree *root,int K){queue<tree*> q; // using stltree* temp;//counting level no & initializing cur_sumint level=0,cur_sum=0; //EnQueue rootq.push(root); //EnQueue NULL to inticate end of 0 levelq.push(NULL);while(!q.empty()){//DeQueueing using STLtemp=q.front(); q.pop();if(temp==NULL){//if current level sum equals to Kif(cur_sum==K) return level;//return level no//ifn't then set cur_sum to 0 for further levelscur_sum=0; if(!q.empty())q.push(NULL);level++;}else{//level order traversalcur_sum+=temp->data; //sum thd levelif(temp->left)q.push(temp->left); //EnQueueif(temp->right)q.push(temp->right); //EnQueue}}return -1; }// creating new node tree* newnode(int data) { tree* node = (tree*)malloc(sizeof(tree)); node->data = data; node->left = NULL; node->right = NULL; return(node); } int main() { //**same tree is builted as shown in example**int c,K;cout<<"Tree is built like the example aforesaid"<<endl;cout<<"input K....."<<endl;cin>>K;tree *root=newnode(2); root->left= newnode(7); root->right= newnode(5); root->right->right=newnode(9);root->right->right->left=newnode(4);root->left->left=newnode(2); root->left->right=newnode(6);root->left->right->left=newnode(5);root->left->right->right=newnode(11);cout<<"finding if any level exists......"<<endl; c=findLevel(root,K);if(c>=0)cout<<"level is found and it is level "<<c<<endl;elsecout<<"level not found, no such tree level exists";return 0; }

Output

输出量

First run: Tree is built like the example aforesaid input K..... 20 finding if any level exists...... level is found and it is level 3 Second run: Tree is built like the example aforesaid input K..... 25 finding if any level exists...... level not found, no such tree level exists

翻译自: https://www.includehelp.com/icp/find-the-level-in-a-binary-tree-with-given-sum-k.aspx

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的在给定总和K的二叉树中找到级别的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。