fork download
copy 
  1. #include <iostream>
  2. #include <stack>
  3. using namespace std;
  4.  
  5. struct TreeNode {
  6.       int val;
  7.       TreeNode *left;
  8.       TreeNode *right;
  9.       TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  10.   };
  11.  
  12. class Solution {
  13. public:
  14.     TreeNode *upsideDownBinaryTree(TreeNode *root) {
  15.         if (root == NULL)
  16.             return root;
  17.         stack<TreeNode*> leftDragon;
  18.         stack<TreeNode*> rightSingle;
  19.         leftDragon.push(root);
  20.         while (root) {
  21.             if (root->left)
  22.                 leftDragon.push(root->left);
  23.             if (root->right)
  24.                 rightSingle.push(root->right);
  25.             root = root->left;
  26.         }
  27.         root = leftDragon.top();
  28.         leftDragon.pop();
  29.         if (!rightSingle.empty()) {
  30.             root->left = rightSingle.top();
  31.             rightSingle.pop();
  32.         }
  33.         TreeNode *cur = root;
  34.         while (!leftDragon.empty()) {
  35.             if (!rightSingle.empty()) {
  36.                 cur->left = rightSingle.top();
  37.                 rightSingle.pop();
  38.             }
  39.             if (!leftDragon.empty()) {
  40.                 cur->right = leftDragon.top();
  41.                 leftDragon.pop();
  42.                 cur = cur->right;
  43.             }
  44.         }
  45.         return root;
  46.     }
  47. };
  48.  
  49. int main() {
  50. 	Solution sol;
  51. 	TreeNode *root = new TreeNode(1);
  52. 	root->left = new TreeNode(2);
  53. 	root = sol.upsideDownBinaryTree(root);
  54. 	cout << root->val << endl;
  55. 	cout << root->right->val << endl;
  56. 	delete root->right;
  57. 	delete root;
  58. 	return 0;
  59. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
1
https://ideone.com/H3KNfy
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!