Solution by temporarily adding parent property


  • 0
    F

    We setup a "parent" property to every node (using a Symbol to avoid any conflict).
    Then, starting from the left most node, we redefine its left and right children using its parent.
    This is the most intuitive solution I found, which is totally legit using JavaScript.

    var parent = Symbol('parent'); 
     
    var upsideDownBinaryTree = function(root) {
        if (!root) { return root; }
        addParents(root);
        let node = getLeftMost(root);
        rotate(node);
        cleanParents(root);
        return node;
    };
    
    function getLeftMost(node) {
        if (!node || !node.left) { return node; }
        return getLeftMost(node.left);
    }
    
    function rotate(node, parent) {
        if (!node) { return node; }
        node.left = node[parent] ? node[parent].right : null;
        node.right = rotate(node[parent]);
        return node;
    }
    
    function addParents(root, p=null) {
        if (!node) { return; }
        node[parent] = p;
        addParents(node.left, root);
        addParents(node.right, root);
    }
    
    function cleanParents(node) {
        if (!node) { return; }
        delete node[parent];
        cleanParents(node.left);
        cleanParents(node.right);
    }
    

Log in to reply
 

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