Data-Structures-and-Algorithms/Trees/flatten-binary-tree-to-linked-list.cpp at main · codemistic/Data-Structures-and-Algorithms · GitHub

Name: Data-Structures-and-Algorithms/Trees/flatten-binary-tree-to-linked-list.cpp at main · codemistic/Data-Structures-and-Algorithms · GitHub
Rating: 4.8 (6973 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>

usingnamespacestd;

/**
 * Question Link:-https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
 * Definition for a binary tree node.
 * struct TreeNode {
 * int val;
 * TreeNode *left;
 * TreeNode *right;
 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
*/

structTreeNode {
int val;
 TreeNode *left;
 TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };

classSolution {
public:

 TreeNode* rightmost(TreeNode* root){
if (root->right==NULL) return root;
returnrightmost(root->right);
 }

voidflatten(TreeNode* root) {
if (root==NULL) return;
 TreeNode* nextright;
 TreeNode* rightMOST;

while (root){

if (root->left){
 rightMOST = rightmost(root->left);
 nextright = root->right;
 root->right = root->left;
 root->left=NULL;
 rightMOST->right=nextright;
 }
 root=root->right;
 }
 }
};