Java Solution Recursive & Non-Recursive


  • 7
    A

    I am ambiguous about if "recursive" is qualified for "in place", as sb in discussion says it's NOT.
    Here I have Java solution in recursive and non-recursive.

    /**
     * Move from root down,
     * for each node, 
     *  attach original right as the right child of the rigthmost node of left subtree,
     *  set original left as new right child.
     * repeat with next right child.
     */
    /// SOLUTION II: non-recursive ///
    public void flatten(TreeNode root) {
        TreeNode node = root;
        while (node != null) {
            TreeNode left = node.left;
            TreeNode right = node.right;
            if (left != null) {
                TreeNode temp = left;
                while (temp.right != null)
                    temp = temp.right;
                temp.right = right;
                node.right = left;
                node.left = null;
            }
            node = node.right;
        }
    }
    
    /// SOLUTION I: accepted, recursion ///
    public void flatten(TreeNode root) {
        if (root == null)
            return;
        TreeNode left = root.left;
        TreeNode right = root.right;
        if (left != null) {
            TreeNode rightmost = getRightmost(left);
            rightmost.right = right;
            root.left = null; // CATCH: must set left to null explicitly
            root.right = left;
        }
        flatten(root.right);
    }
    
    // return the rightmost node of a subtree;
    // node must not be null.
    private TreeNode getRightmost(TreeNode node) {
        while (node.right != null)
            node = node.right;
        return node;
    }

  • 1
    L

    I think the word "in-place" means that one does not create new nodes for the result, but simply change the pointers of nodes in-place.


  • 0
    Y

    This is the clearest solution I've ever seen. Easy to understand. Very smart. Thanks!


  • 0
    M

    Your iterative solution is so clear! Thanks for sharing.


  • 0
    O

    @AlexTheGreat You non-recursive solution is so easy to understand. Thx


Log in to reply
 

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