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.

It is quite easy to find LeetCode problem solutions online. Just Google for leetcode 114 solution java. First result I got was: walkccc.me/LeetCode/problems/0114 I suggest that you compare your solution with theirs. — Abra
– Abra, Commented Sep 30, 2023 at 13:44
I have actually solved it using another approach. I was just wondering why root = res was not updating the root in this particular solution. — hermit
– hermit, Commented Sep 30, 2023 at 14:24
It's reasonable that you included the information from your debugger variable explorer as an image. But, could you, please, include example input, output, and expected as text? Images of text are not well received here. — Old Dog Programmer
– Old Dog Programmer, Commented Sep 30, 2023 at 16:02

pixel · Accepted Answer · 2023-09-30 11:04:00Z

0

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.

answered Sep 30, 2023 at 11:04

pixel

1,0691 gold badge3 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

hermit Over a year ago

Have you tried submitting your solution in leetcode? It is not giving correct result.

pixel Over a year ago

i don't have an account, tell me where it fails?

Collectives™ on Stack Overflow

Leetcode question: Flatten binary tree into linkedlist

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related