Concise C++ recursion solution


  • 3
    N
    class Solution {
    public:
        void flatten(TreeNode* root) {
            if (!root) return;
            if (root->left){
                flatten(root->left);
                ptr->right = root->right;
                root->right = root->left;
                root->left = NULL;
            }
            ptr = root;
            flatten(root->right);
        }
    private:
        TreeNode* ptr;
    };

  • 5
    class Solution {
    private:
        TreeNode *tail;
    public:
        void flatten(TreeNode *root) {
            if (!root) return;
            tail = root;
            if (root->left) {
                flatten(root->left);
                tail->right = root->right;
                root->right = root->left;
                root->left = NULL;
            }
            flatten(tail->right);
        }
    };
    

    Minor change based on your code. tail denotes the last node of the preorder sequence of subtree root->left.

    The pre-order traversal structure is clearer. Visit the root (tail = root), then visit left subtree and then right subtree.

    IMHO, this code is a little bit faster than yours because the line flatten(root->right); in your code will result in useless recursive calls.


Log in to reply
 

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