156. Binary Tree Upside Down - cocoder39/coco39_LC GitHub Wiki

156. Binary Tree Upside Down

   root
    1
   / \
  2   3
 / \
4   5

  top  root
   4   1
  / \ / \
 5   2   3
   root->left 

   4
  / \
 5   2
    / \
   3   1  

"all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty": 1 no right node 2 if there is right node, there must be left node. Hence terminal case root->left == nullptr indicates root is a leave node. After upside-down, all the left nodes are either leaf nodes with a sibling (a right node that shares the same parent node) or empty

T(n) = T(left) + 1 = T(n - 1) + 1 = O(n), space is O(height) = O(n)

TreeNode* upsideDownBinaryTree(TreeNode* root) {
        if (! root || ! root->left) {
            return root;
        }
      
        TreeNode* top = upsideDownBinaryTree(root->left); //return the root of upsideDownBinaryTree
        
        root->left->left = root->right;
        root->left->right = root;
        root->left = nullptr;
        root->right = nullptr;
        return top;
    }

method 2: top-down iteration.

    1
   / \
  2   3
 / \
4   5

cur 1             next  2          new_left 3
   / \                 / \
  #   #               4   5

cur 2             next  4          new_left 5
   / \                  
  3   1                  

   4
  / \
 5   2
    / \
   3   1  

O(n) time and O(1) space

TreeNode* upsideDownBinaryTree(TreeNode* root) {
        TreeNode* cur = root;
        TreeNode* new_right = nullptr;
        TreeNode* new_left = nullptr;
        
        while (cur) {
            TreeNode* left = cur->left;
            cur->left = new_left;
            
            TreeNode* right = cur->right;
            cur->right = new_right;
            
            new_right = cur;
            new_left = right;
            cur = left;
        }
        return new_right;
    }