Help for a tree problem

[landlord2017]

LeetCode challenge question (https://leetcode.com/problems/flatten-binary-tree-to-linked-list/?tab=Description):

114. Flatten Binary Tree to Linked List

Above is the problem for the tree problem I am practicing on LeetCode.

Below is my code. I think I did everything right, but actually not. I have tried this code on both Leetcode online compiler and my own Xcode IDE. Neither works. It seems I have dynamically created TreeNode and linked them properly? and after I reassigned the root and returned it, everything screwed.....

Please help. I am a bit frustrated...Of course there is some online solution. But I want to make it works in my own way and know why it does not...

L

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root)
    {
        if (!root){return;}
//        TreeNode dummy(0);
//        TreeNode* res=&dummy;
        TreeNode *res=new TreeNode(0);
        TreeNode *resRoot=res;
        preorderFlatten(root,res);
        
        root=resRoot;
        root->left=nullptr;
        cout<<endl;
//        while(root)
//        {
//            cout<<root->val<<" ";
//            root=root->right;
//        }
    }
    void preorderFlatten(TreeNode* head,TreeNode* res)
    {
        if (!head){return;}
        res->right=new TreeNode(head->val);
        //res->val=head->val;
        
        res=res->right;
        res->left=nullptr;
        cout<<res->val<<" "<<res<<endl;
        preorderFlatten(head->left,res);
        preorderFlatten(head->right,res);
        return;
    }
};

[cire]

Just looking at these lines:

        TreeNode *res=new TreeNode(0);
        TreeNode *resRoot=res;
        preorderFlatten(root,res);
        
        root=resRoot;

root now points to a TreeNode with a 0 value. No node in the original tree had a 0 value. More importantly, root is a local variable and any changes to it are lost when the function flatten returns. There is no need to allocate any new nodes here at all. All that is required is the rearrangement of existing ones.

I would suggest mapping out your strategy before coding it instead of trying to code by the seat of your pants. ;)

[landlord2017]

I was trying to create a memory to copy the tree into a single link. I have read some good solutions and known my method is not efficient. But I want to know why my method does not work.

I thought the root is assigning to a new memory I created. The new memory should store expected information. But it is now.....

[cire]

I was trying to create a memory to copy the tree into a single link.

You cannot copy an entire tree into a single leak link.

But I want to know why my method does not work.

Because it's wrong. Again, I would suggest mapping out your strategy before coding it.

I thought the root is assigning to a new memory I created.

Again, the root variable in your function is local to the function. Assigning to it does not affect any other pointer in the program.

Consider that main in the following snippet is similar to the testing code calling your function...
http://ideone.com/0oW76T
Main doesn't see the changes you make. Note that different variables co-existing have different addresses which is why the tree and root variables don't have the same address.

[dhayden]

It looks like your intention is for res to always be the tail of the list. That means it should be passed as a reference so you're always updating the same variable:
void preorderFlatten(TreeNode* head,TreeNode* &res)

But you still need to keep track of the head of the list before calling preorderFlatten(). Something like:

    TreeNode *res=new TreeNode(0);
    TreeNode *head{res};
    preorderFlatten(root,res);
    return head;

When I do code like that, I get the flattened tree, except that it also has the pesky 0 node at the start of the list.

FWIW, here's some code I came up with to flatten the list without creating any new nodes:

// flatten binary tree and return a reference to the nullptr at the tail of the list.
// The idea is to flatten the left and right sides, and then attach the right list to the tail
// of the left one.
TreeNode * &flatten(TreeNode * &root)
{
    if (root == NULL) {
        return root;
    }

    TreeNode * &leftTail { flatten(root->left) };
    TreeNode * &rightTail { flatten(root->right) };
    leftTail = root->right;   // append the right list to the left one.
    root->right = root->left; // move the left list to the right side of the node
    root->left = nullptr;     // null out the left pointer
    return rightTail;         // return the tail of the right side, now the tail of the whole list.
}

[landlord2017]

Ok. I see. I thought a pointer can be preserved and passed in or out of the function. I never use *& ptr, kind of passing. This is something new to me and I have to learn. I will try this in details.

Thank you,

L

[dhayden]

When you pass a pointer to a function, you can change the thing that it points to and that will be reflected everywhere in the program. But if you change the pointer itself (so it points to something else) then that won't be reflected in the parameter that you pass:

int x,y;
void f(int *ip2)
{
   ip2 = &y;  // ip2 points to y
}

int main()
{
    int *ip = &x;  // ip points to x
    f(ip);
   // ip still points to x.
}

If you think about this, it's just like any other parameter. Parameters are normally passed by value, whether they are ints, doubles, or pointers.

Now you can change this by passing a parameter by reference:
void f(int &i);

Now any change that you make to i inside f() will also change whatever variable was passed into f.

That syntax works for any parameter type. So if you can pass a pointer by value like this:
void f(int *ip);
then you can a pointer by reference like this:
void f(int * &ip);
Now changes that you make the pointer itself inside f() will also change whatever variable was passed into f.

[landlord2017]

Amazing! Great explanations with great examples. I learned a lot.

Thank you very much!

L