Share my C++ solution,easy to understand


  • 0
    V

    Recursion:

    class Solution {
    public:
        void flatten(TreeNode* root) {
            if (root == NULL)
                return;
            
            TreeNode *last = NULL;
            flattenTree(root, last);
        }
        
        TreeNode* flattenTree(TreeNode *root, TreeNode* &last)
        {
            if (root == NULL)
                return NULL;
            
            if (last != NULL)
            {
                last->right = root;
                last->left = NULL;
            }
            last = root;
            
            TreeNode *left = root->left;
            TreeNode *right = root->right;
            
            flattenTree(left, last);
            flattenTree(right, last);
        }
    };

  • 0
    V

    Iteration:

    class Solution {
    public:
        void flatten(TreeNode* root) {
            if (root == NULL)
                return;
            
            TreeNode *cur = root;
            TreeNode *last = NULL;
            
            while (cur != NULL)
            {
                if (cur->left != NULL)
                {
                    last = cur->left;
                    while (last->right != NULL)
                        last = last->right;//last : the right-most node of the left subtree
                    
                    last->right = cur->right;
                    cur->right = cur->left;
                    cur->left = NULL;
                }
                cur = cur->right;
            }
        }
    };

Log in to reply
 

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