### 技术控

今日:1| 主题:51205

# [其他] Swap Nodes in Binary tree of every k’th level

97 1

### 立即注册CoLaBug.com会员，免费获得投稿人的专业资料，享用更多功能，玩转个人品牌！

x
Given a binary tree and integer value k, the task is to swap sibling nodes of every k’th level where k >= 1.
Examples:
1. Input :  k = 2  and Root of below tree
2.       1             Level 1
3.     /   \
4.    2     3          Level 2
5. /     /   \
6. 4     7     8       Level 3

7. Output : Root of the following modified tree
8.       1
9.     /   \
10.    3     2
11. /  \   /
12. 7    8  4
13. Explanation : We need to swap left and right sibling
14.               every second level. There is only one
15.               even level with nodes to be swapped are
16.               2 and 3.

17. Input : k = 1 and Root of following tree
18.
19.        1          Level 1
20.      /   \
21.     2     3       Level 2
22.   /  \
23. 4    5           Level 3
24. Output : Root of the following modified tree
25.        1
26.      /   \
27.     3     2
28.          /  \
29.         5    4
30. Since k is 1, we need to swap sibling nodes of
31. all levels.

A    simple solutionof this problem is that for each is to find sibling nodes for each multiple of k and swap them.
An    efficient solutionis to keep track of level number in recursive calls. And for every node being visited, check if level number of its children is a multiple of k. If yes, then swap the two children of the node. Else, recur for left and right children.
Below is C++ implementation of above idea
1. // c++ program swap nodes
2. #include<bits/stdc++.h>
3. using namespace std;

4. // A Binary Tree Node
5. struct Node
6. {
7.     int data;
8.     struct Node *left, *right;
9. };

10. // function to create a new tree node
11. Node* newNode(int data)
12. {
13.     Node *temp = new Node;
14.     temp->data = data;
15.     temp->left = temp->right = NULL;
16.     return temp;
17. }

18. // swap two Node
19. void Swap( Node **a , Node **b)
20. {
21.     Node * temp = *a;
22.     *a = *b;
23.     *b = temp;
24. }

25. // A utility function swap left- node & right node of tree
26. // of every k'th level
27. void swapEveryKLevelUtil( Node *root, int level, int k)
28. {
29.     // base case
30.     if (root== NULL ||
31.             (root->left==NULL && root->right==NULL) )
32.         return ;

33.     //if current level + 1  is present in swap vector
34.     //then we swap left & right node
35.     if ( (level + 1) % k == 0)
36.         Swap(&root->left, &root->right);

37.     // Recur for left and right subtrees
38.     swapEveryKLevelUtil(root->left, level+1, k);
39.     swapEveryKLevelUtil(root->right, level+1, k);
40. }

41. // This function mainly calls recursive function
42. // swapEveryKLevelUtil()
43. void swapEveryKLevel(Node *root, int k)
44. {
45.     // call swapEveryKLevelUtil function with
46.     // initial level as 1.
47.     swapEveryKLevelUtil(root, 1, k);
48. }

49. // Utility method for inorder tree traversal
50. void inorder(Node *root)
51. {
52.     if (root == NULL)
53.         return;
54.     inorder(root->left);
55.     cout << root->data << " ";
56.     inorder(root->right);
57. }

58. // Driver Code
59. int main()
60. {
61.     /*    1
62.         /   \
63.        2     3
64.      /      /  \
65.     4      7    8   */
66.     struct Node *root = newNode(1);
67.     root->left = newNode(2);
68.     root->right = newNode(3);
69.     root->left->left = newNode(4);
70.     root->right->right = newNode(8);
71.     root->right->left = newNode(7);

72.     int k = 2;
73.     cout << "Before swap node :"<<endl;
74.     inorder(root);

75.     swapEveryKLevel(root, k);

76.     cout << "\nAfter swap Node :" << endl;
77.     inorder(root);
78.     return 0;
79. }

Output:

1. Before swap node :
2. 4 2 1 7 3 8
3. After swap Node :
4. 7 3 8 1 4 2

This article is contributed by    Nishant_singh(pintu). If you like GeeksforGeeks and would like to contribute, you can also write an article using    contribute.geeksforgeeks.orgor mail your article to [email protected] See your article appearing on the GeeksforGeeks main page and help other Geeks.

 是爷们的娘们的都帮顶！大力支持

• ## 2017支付宝集五福在哪扫福字怎么扫福字 支

支付宝在哪扫福字?2017集福怎么扫福字?今天支付 [...]

• ## 2017支付宝福卡怎么获得 2017支付宝如何集

2017支付宝福卡怎么获得呢?本文小编为您带来2017 [...]

• ## 2017年支付宝集五福攻略：Get到这两点轻松

开篇之前告诉大家一个可能会比较嫌弃的消息，为 [...]

• ## How Your Startup Can Leverage Big Brands

At CES 2017, I hosted a panel with Amazon, [...]

• ## 在百度，有哪件大事是非陆奇不可的？

昨天，雷锋网 (公众号：雷锋网) 第一件事 [...]

• ## 闭着眼睛走你也不会迷路 微信背景图片

优秀的人就像一团光芒，和他们呆久了，也就 [...]

• ## 刚刚 京东发布2017年生活服务类目招商规则

【亿邦动力网讯】1月18日消息，昨晚，亿邦动力网 [...]

• ## 2017支付宝过年福集五福活动在哪里?支付宝

2017支付宝过年福集五福活动在哪里?支付宝过年福 [...]

• ## ZANK同志报告《2016LGBTA群体恋爱婚姻观白

国内最大的同志服务平台ZANK于月初在网络上发布 [...]

• ## 2017支付宝集五福怎么玩 2017支付宝集五福

2017年支付宝又推出了集五福活动，不过放心，今 [...]

© 2001-2017 Comsenz Inc. Design: Dean. DiscuzFans.