Leetcode question: Flatten binary tree into linkedlist

Question

I am trying to solve this problem on leetcode: https://leetcode.com/problems/flatten-binary-tree-to-linked-list/ (Flatten binary tree into linkedlist)

This is my code:

class Solution{
   
    TreeNode result;

    public void flatten(TreeNode root) {
        TreeNode res = flattenTree(root, null);
        root = res;
    }

    private TreeNode flattenTree(TreeNode node, TreeNode temp) {

        if (node == null) {
            return node;
        }

        if (result == null) {
            result = new TreeNode(node.val);
            temp = result;
        } else {
            TreeNode result1 = new TreeNode(node.val);
            result.right = result1;
            result = result.right;
            result.left = null;
        }
        flattenTree2(node.left, temp);
        flattenTree2(node.right, temp);
        return temp;
    }
}

I believe this is the correct solution because after pointing to res, root contains the tree in correct format for example input data shown in the first screenshot. This, is the screenshot of inspecting the tree after the method executes.

But, still I am getting incorrect answer. The leetcode compiler says that the root has not changed at all. This is the outcome.

Not, sure what I need to do to make leetcode accept is as the correct solution.

Answer 1

The issue is you're updating the root variable inside the flatten method. In your code, you're updating the root parameter, which is a local variable within the flatten method, but this change won't affect the original root outside the method. To achieve the desired result, you should modify the tree structure directly instead of trying to reassign the root parameter.

updated code:

class Solution {
    public void flatten(TreeNode root) {
        flattenTree(root);
    }

    private TreeNode flattenTree(TreeNode node) {
        if (node == null) {
            return null;
        }

        TreeNode rightSubtree = node.right;

        if (node.left != null) {
            node.right = node.left;
            node.left = null;
            TreeNode lastRight = flattenTree(node.right);
            lastRight.right = rightSubtree;
        }

        if (rightSubtree != null) {
            return flattenTree(rightSubtree);
        }

        return node;
    }
}

above code will modifies the tree structure in place by recursively flattening the left and right subtrees and updating the right pointers accordingly. It doesn't need to return any new nodes or trees, as it directly modifies the input root.