Iterative and recursive solutions in Java


  • 0
    X

    Note that at each step, we are basically assigning:

    node.left = parent.right;
    node.right = parent
    

    It's not hard to come up with two solutions based on this idea.

    // Iterative approach  
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        TreeNode cur = root, parent = null, parentRight = null;
        while (cur != null) {
            TreeNode left = cur.left;
            cur.left = parentRight;
            parentRight = cur.right;
            cur.right = parent;
            parent = cur;
            cur = left;
        }
        return parent;
    }
    
    // Recursive approach
    private TreeNode help(TreeNode node, TreeNode parent) {
        if (node == null) return parent;
        TreeNode root = help(node.left, node);
        node.left = parent == null ? null : parent.right;
        node.right = parent;
        return root;
    }
    
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        return help(root, null);
    }

Log in to reply
 

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