My C++ recursive solution


  • 0
    D

    The basic idea is to flatten the left subtree and hook it back to the root, and then flatten the right subtree and hook it back to the last node of the left subtree.

      class Solution {
        public:
            void flatten(TreeNode *root) {
                TreeNode *head, *tail;
                if(root)
                {
                    flattenTree(root);
                }
            }
        
        //the returned value is the last node of the flattened list, needed when hooking it back to the original list     
            TreeNode * flattenTree(TreeNode *root)
            {
                TreeNode *tail,*r_child;
                tail = root;
                if(root)
                {
                    r_child = root->right;
                    // first flatten the left subtree and hook it back
                    if(root->left)
                    {
                        root->right = root->left; // hook back to the root node
                        tail = flattenTree(root->left); // flattern 
                        root->left = NULL;
                    }
                    // then flatten the right subtree and hook it back
                    if(r_child)
                    {
                        tail->right = r_child; // hook back to the last node of the left subtree
                        tail->left = NULL;
                        tail = flattenTree(r_child); // flatten
                    }
                }
                
                return tail;
            }
        };

Log in to reply
 

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