### 技术控

今日:211| 主题:58086

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

125 1
 Given a binary tree and integer value k, the task is to swap sibling nodes of every k’th level where k >= 1.   Examples: Input :  k = 2  and Root of below tree                            1             Level 1     /   \    2     3          Level 2 /     /   \ 4     7     8       Level 3 Output : Root of the following modified tree       1     /   \    3     2 /  \   /   7    8  4 Explanation : We need to swap left and right sibling               every second level. There is only one               even level with nodes to be swapped are               2 and 3. Input : k = 1 and Root of following tree                     1          Level 1      /   \     2     3       Level 2   /  \ 4    5           Level 3 Output : Root of the following modified tree        1      /   \     3     2          /  \         5    4 Since k is 1, we need to swap sibling nodes of 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 // c++ program swap nodes #include using namespace std; // A Binary Tree Node struct Node {     int data;     struct Node *left, *right; }; // function to create a new tree node Node* newNode(int data) {     Node *temp = new Node;     temp->data = data;     temp->left = temp->right = NULL;     return temp; } // swap two Node void Swap( Node **a , Node **b) {     Node * temp = *a;     *a = *b;     *b = temp; } // A utility function swap left- node & right node of tree // of every k'th level void swapEveryKLevelUtil( Node *root, int level, int k) {     // base case     if (root== NULL ||             (root->left==NULL && root->right==NULL) )         return ;     //if current level + 1  is present in swap vector     //then we swap left & right node     if ( (level + 1) % k == 0)         Swap(&root->left, &root->right);     // Recur for left and right subtrees     swapEveryKLevelUtil(root->left, level+1, k);     swapEveryKLevelUtil(root->right, level+1, k); } // This function mainly calls recursive function // swapEveryKLevelUtil() void swapEveryKLevel(Node *root, int k) {     // call swapEveryKLevelUtil function with     // initial level as 1.     swapEveryKLevelUtil(root, 1, k); } // Utility method for inorder tree traversal void inorder(Node *root) {     if (root == NULL)         return;     inorder(root->left);     cout << root->data << " ";     inorder(root->right); } // Driver Code int main() {     /*    1         /   \        2     3      /      /  \     4      7    8   */     struct Node *root = newNode(1);     root->left = newNode(2);     root->right = newNode(3);     root->left->left = newNode(4);     root->right->right = newNode(8);     root->right->left = newNode(7);     int k = 2;     cout << "Before swap node :"<

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

• ## 万字长文 | 共享汽车的宿命

如今共享经济与各行各业都有扯不清的关系， [...]

• ## 这部披着日剧外衣的美妆穿搭教程火了！人10

微信号 yokacom 最 [...]

• ## Spring MVC 之使用 Freemarker

Freemarker 是使用比较广泛的模板，本文介绍如何 [...]

• ## 2017超流行十款发色推荐，炎炎夏日就要“色

微信号 jnntf001 [...]

• ## 这些女孩子最喜欢的烫卷发，你在家也能做！

微信号 jp121216 长 [...]

• ## 三男三女海滩play，你们儿时X启蒙终于回来

微信号 CCTV6_m1905 [...]

• ## 被顶级化妆师摸过的女人，都变成了女神

微信号 diany233 关 [...]

• ## 睡不着？Sana智能护目镜让您摆脱失眠困扰

相信大部分人都有过失眠的体验，虽然失眠只是一 [...]

• ## 安迪睡衣都奢华，曲妖精全套奢侈大牌，却都

微信号 ilove8po 延 [...]

• ## OFF-WHITE又放大招，“警戒线”手袋全新配

微信号 MFashionChi [...]