Flatten binary tree to linked list code not working-CodePudding

So, I was trying to do this leetcode problem about flatten binary tree to linked list. I used a vector to store the preorder traversal of the tree and then create a new tree whole left child is always null and right child has the value. But the problem I am facing is that my code is not updating the root node in the main function. The output is always printing the original tree despite i do any change in root node inside the function. The code is as below:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    
    vector<int>res;
    
    void preOrder(TreeNode *root){
        if(root == NULL)return;
        res.push_back(root->val);
        
        preOrder(root->left);
        preOrder(root->right);
    }
    
    void flatten(TreeNode* root) {
        preOrder(root);
        
        TreeNode *nh = NULL, *ptr;
        
        for(int i = 0; i < res.size()-2; i  ){
            TreeNode *node = new TreeNode(res[i]);
            
            if(nh == NULL){
                nh = node;
                ptr = nh;
            }else{
                ptr->right = node;
                ptr = ptr->right;
            }
        }
        
        root = nh;
    }
};

CodePudding user response：

You need to use

TreeNode * flatten(TreeNode* root); // returns flattened tree

You should not be using vector<int>res;. If you build a new tree then allocate the tree nodes directly during traversal and and pass a TreeNode*& tail to preOrder to append new nodes to.

PS: I would call that flattened, flatten sorts like you modify the tree directly.

Alternatively you can flatten the tree in-place by shuffling around the existing TreeNodes:

// modify `root` to be preOrder and return tail
TreeNode *& preOrder(TreeNode *root) {
    if (root->left == nullptr) {
        if (root->right == nullptr) {
            // attach further nodes to the right
            return root->right;
        } else {
            // only right child, keep going
            return preOrder(root->right);
        }
    } else {
        if (root->right == nullptr) {
            // only left child, move to right and keep going
            root->right = root->left;
            return preOrder(root->right);
        } else {
            // left and right child
            // preOrder the left and remember the tail
            TreeNode *&tail = preOrder(root->left);
            // attach right child to the tail
            tail = root->right;
            // move ordered left child to the right
            root->right = root->left;
            root->left = nullptr;
            // preOrder the right child and return its tail
            return preOrder(tail);
        }
    }
}

void flatten(TreeNode *root) {
    if (root == nullptr) return;
    preOrder(root);
}

CodePudding user response：

Changing the last line of your flatten function into

*root = *nh;

cuz root and nh are both pointers and you want to assign their new values by using the * operator.
And adjust your for loop

for(int i = 0; i < res.size(); i  )

since you don't want to miss any node in the vector.
And then add

if (root == NULL) return;

to solve runtime error when the root is NULL. I passed by adding these modifications.