Clean Java solution


  • 90
    public TreeNode upsideDownBinaryTree(TreeNode root) {
      if (root == null || root.left == null && root.right == null)
        return root;
    
      TreeNode newRoot = upsideDownBinaryTree(root.left);
      
      root.left.left = root.right;
      root.left.right = root;
      
      root.left = null;
      root.right = null;
          
      return newRoot;
    }

  • 0
    M

    Thank you for sharing! Nice recursion!


  • 0
    2

    C++ implementation of your method

      class Solution {
        public:
            TreeNode* upsideDownBinaryTree(TreeNode* root) {
                if(root == NULL || (root->left == NULL && root->right == NULL) )
                    return root;
                TreeNode* new_root = upsideDownBinaryTree(root->left);
                root->left->left = root->right;
                root->left->right = root;
                root->left = NULL;
                root->right = NULL;
                return new_root;
            }
        };

  • 0

    What if the root node only has child on the right so that roo->left == null?
    Will the statement root.left.left get pointer error?


  • 1
    4

    @yubad2000 said in Clean Java solution:

    What if the root node only has child on the right so that roo->left == null?

    That is not possible as the question clearly states "Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty"


  • -1
    R

    @yubad2000 the first line is protecting this situation.


  • 1
    D

    @jeantimex said in Clean Java solution:

    if (root == null || root.left == null && root.right == null)

    actually you can change this line to
    if (root == null || root.left == null)
    because if the left child is null, then the right child must be null.


  • 0
    F

    You did a perfect job!


  • 1

    I have a question: why can't we use newNode.left = root.right, instead of root.left.left = root.right;?


  • 1
    R

    @chidong Because the node you return is newRoot, which will always be the left most node. You can not modify it multiple times.


  • 0
    C

    what if the root has only 2 children? Wouldn't root.left.left be null?


  • 0

    @crrapran

    what if the root has only 2 children? Wouldn't root.left.left be null?

    It's OK to be null, because you are assigning to it instead of referencing it. The root.left is ensured not null as it is checked at the very beginning.


    I have another question for the author though, why do you need && root.right == null. if root.left is null, root.right is guaranteed to be null, isn't it?


  • 0
    H

    What would be the runtime of this algorithm?


  • 0
    X
    This post is deleted!

  • 0
    K

    Why should we clean the children of root before return?


  • 1

    alt text

        public TreeNode upsideDownBinaryTree(TreeNode root) {
          if(root == null || root.left == null && root.right == null) return root;
          TreeNode res = upsideDownBinaryTree(root.left);
          root.left.left = root.right;
          root.left.right = root;
          root.left = null;
          root.right = null;
          return res;  
        }

  • 1
    F

    Can you explain what if the tree is like following shape?

              1
            /   \
          2     3
         /      /  \
       4       5    6
    

    I think this tree is qualified with the definition of the problem.
    But your solution will return

                  4
                    \
                     2
                    /  \
                  3    1
                 / \
               5   6
    

    while the Node 6 is still a right node.
    So my solution is very similar to you, but add one line to rotate root.right too:

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public TreeNode upsideDownBinaryTree(TreeNode root) {
            if (root == null) {
                return null;
            }
            if (root.left == null) {
                return root;
            }
            TreeNode newRoot = upsideDownBinaryTree(root.left);
            TreeNode newLeft = upsideDownBinaryTree(root.right);   // This line rotate the right node
            root.left.left = newLeft;
            root.left.right = root;
            root.left = null;
            root.right = null;
            return newRoot;
        }
    }
    

    Both of our solutions can pass the OJ, I just want to know if there any parts I misunderstand.


Log in to reply
 

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