Simplest C++ recursion solution


  • 0
    D
    TreeNode *lastpre = NULL;
    void flatten(TreeNode *root) {
        if(root==NULL)
            return;
        lastpre = root;
        if(root->left==NULL && root->right==NULL)
            return;
        if(root->left==NULL) {
            flatten(root->right);
            return;
        }
        
        TreeNode* rNode = root->right;
        root->right = root->left;
        root->left = NULL;
        flatten(root->right);
        lastpre->right = rNode;
        flatten(rNode);
    }

  • 0
    F

    "lastpre = root;" is for "lastpre->right = rNode;", because this problem need pre-order traversal.

    TreeNode* rNode = root->right;
    root->right = root->left;
    root->left = NULL;
    the code above mean put left tree to right tree for pre-order traversal when the left tree is not null.

    And then ,flatten(root->right); first deal with the new right tree ,the old left tree,
    next , lastpre->right = rNode; put old right tree to the new right tree's end,
    finally , flatten(rNode); deal with old right tree.


  • 0

Log in to reply
 

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