Explain the question and my solution, Python


  • 28
    O

    I need to admit that I totally didn't get how to do the "upside-down"

    After some struggling and googling, I saw the graph in binary tree representation of trees.

    It's not directly the same, but give me a sense of how to do it.

    The transform of the base three-node case is like below:

                             Root                   L
                             /  \                  /  \
                            L    R                R   Root
    

    You can image you grab the L to the top, then the Root becomes it's right node, and the R becomes its left node.

    Knowing the base case, you can solve it recursively.

    How? You keep finding the left most node, make it upside-down, then make its parent to be its right most subtree recursively.

    Here is a small point to be noticed, when you connect the root to the right subtree, you need to make sure you are not copying the original root, otherwise it will become cyclic!

    def upsideDownBinaryTree(self, root):
        if not root or not root.left:
            return root
        lRoot = self.upsideDownBinaryTree(root.left)
        rMost = lRoot
        while rMost.right:
            rMost = rMost.right
        root, rMost.left, rMost.right = lRoot, root.right, TreeNode(root.val)
        return root

  • 0
    L

    Java version:

    public class Solution {
        public TreeNode upsideDownBinaryTree(TreeNode root) {
            if (root == null || root.left == null)
                return root;
            TreeNode newRoot = upsideDownBinaryTree(root.left);
            TreeNode rightMostIterator = newRoot;
            while (rightMostIterator.right != null) {
                rightMostIterator = rightMostIterator.right;
            }
            rightMostIterator.left = root.right;
            rightMostIterator.right = new TreeNode(root.val);
            return newRoot;
        }
    }

  • 0
    Z
    This post is deleted!

  • 0
    Z

    Actually, you can also return rMost in each iteration such that you don't need to find rMost from the root every time.

    def upsideDownBinaryTree(self, root):
            if not root or not root.left:
                    return root
            
            def updown(root):
                if not root or not root.left:
                    return root,root
                    
                lRoot,rMost = updown(root.left)  
                
                rMost.left, rMost.right = root.right, TreeNode(root.val)
                return lRoot,rMost.right
            
            result,rMost=updown(root)
            return result
    

  • 0
    Z

    A better version. You don't need to new TreeNode:

    def upsideDownBinaryTree(self, root):
            if not root or not root.left:
                    return root
            
            def updown(root):
                if not root or not root.left:
                    return root,root
                    
                lRoot,rMost = updown(root.left)  
            
                rMost.left  = root.right
                root.left=None
                root.right=None
                rMost.right = root
                
                
                return lRoot,rMost.right
            
            result,rMost=updown(root)
            return result
    

  • 0
    D

    @orbuluh I really like your solution!
    I am just curious about its time complexity.
    I think that the worst time complexity for the recursion part would be O(logN) (where n is the number of nodes) and the while loop part is also O(logN) for the worst case. Therefore, the time complexity is going to be O(logN).
    Am I understanding it correctly?

    Thank you so much!


Log in to reply
 

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