
#include <bits/stdc++.h>
using namespace std;
  
struct TreeNode {
    int val = 0;
    TreeNode* left;
    TreeNode* right;
  
    
    TreeNode(int x)
    {
        val = x;
        left = right = NULL;
    }
};
  
void printTree(TreeNode* root)
{
    if (!root)
        return;
  
    
    printTree(root->left);
  
    
    cout << root->val << " ";
  
    
    printTree(root->right);
}
  
TreeNode* shiftRight(TreeNode* root)
{
  
    
    if (!root)
        return NULL;
  
    stack<TreeNode*> st;
    queue<TreeNode*> q;
  
    
    if (root->right)
        q.push(root->right);
  
    root->right = NULL;
  
    
    if (root->left)
        q.push(root->left);
  
    root->left = NULL;
  
    
    st.push(root);
  
    while (!q.empty()) {
  
        
        
        int n = q.size();
        stack<TreeNode*> temp;
  
        
        
        while (n--) {
  
            
            if (!st.top()->right)
  
                
                
                st.top()->right = q.front();
  
            
            else {
  
                
                st.top()->left = q.front();
  
                
                
                st.pop();
            }
  
            
            if (q.front()->right)
  
                
                q.push(q.front()->right);
  
            
            q.front()->right = NULL;
  
            
            if (q.front()->left)
  
                
                q.push(q.front()->left);
  
            
            q.front()->left = NULL;
  
            
            
            
            temp.push(q.front());
            q.pop();
        }
  
        while (!st.empty())
            st.pop();
  
        
        
        while (!temp.empty()) {
  
            st.push(temp.top());
            temp.pop();
        }
    }
  
    
    
    return root;
}
  
int main()
{
  
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);
  
    
    root = shiftRight(root);
  
    
    printTree(root);
  
    return 0;
}
 
 
 
 
0 comments:
Post a Comment