C++ implementation with comments @ Rainbow


  • 0

    This is referred from the top voted solution but it contains no comments, which is not easy to understand at the frist glance as it is not that trival.

    So I add some comments to help you know why use the prev , why choose this order, If you still find this solution not understood, Please refer the second solution below . The second solution just mimic all the precedure and easy to understand.

    Solution 1

    class Solution {
    private:
        //let the prev pointer point to the traversal returned first node
        //our traversal order is : right -> left -> root
        //the prev will point to the last node visited after visiting left subtree and right subtree
        TreeNode* prev = nullptr;
    public:
        void flatten(TreeNode* root) {
            if (root == nullptr)
                return;
            flatten(root->right);
            flatten(root->left);
            root->right = prev;
            root->left = nullptr;
            prev = root;
        }
    };
    

    Solution 2

    class Solution {
    public:
        void flatten(TreeNode* root) {
            if (root == nullptr)  return;
            TreeNode* left = root->left;
            TreeNode* right = root->right;
            root->left = nullptr;
            flatten(left);
            flatten(right);
            root->right = left;
            TreeNode* cur = root;
            while (cur->right) cur = cur->right;
            cur->right = right;
        }
    };
    

Log in to reply
 

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