C++ 2 solutions recursive/iterative O(n) time complexity


  • 0
    D
    class Solution {
    public:
        TreeNode* upsideDownBinaryTree(TreeNode* root) {
            if(!root || !root -> left) return root;
            TreeNode* left_sub = upsideDownBinaryTree(root -> left);
            root -> left -> right = root;
            root -> left -> left = root -> right;
            root -> left = root -> right = nullptr;
            return left_sub;
        }
    };
    
    class Solution {
    public:
        TreeNode* upsideDownBinaryTree(TreeNode* root) {
            TreeNode* curr = root, *next = nullptr, *prev = nullptr, *last_right_leaf = nullptr;
            while(curr) {
                next = curr -> left;
                curr -> left = last_right_leaf;
                last_right_leaf = curr -> right;
                curr -> right = prev;
                prev = curr;
                curr = next;
            }
            return prev;
        }
    };
    

    Iterative solution comes from here


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.