C++

Traverse

1 /** 2  * Definition of TreeNode: 3  * class TreeNode { 4  * public: 5  *     int val; 6  *     TreeNode *left, *right; 7  *     TreeNode(int val) { 8  *         this->val = val; 9  *         this->left = this->right = NULL;10  *     }11  * }12  */13 class Solution {14 public:15     /**16      * @param root: a TreeNode, the root of the binary tree17      * @return: nothing18      */19     void flatten(TreeNode *root) {20         if(!root) return;21         vector
     
       allNodes;22         preorder(root, allNodes);23         int n = allNodes.size();24         for(int i=0; i
      
       left = NULL;26             allNodes[i]->right = allNodes[i+1];27         }28         allNodes[n-1]->left = allNodes[n-1]->right = NULL;29     }30     31     void preorder(TreeNode *root, vector
       
         &allNodes) {32         if(!root) return;33         allNodes.push_back(root);34         preorder(root->left, allNodes);35         preorder(root->right, allNodes);36     }37 };
       
      
     

C++

Divide-Conquer

Recursive

1 /** 2  * Definition of TreeNode: 3  * class TreeNode { 4  * public: 5  *     int val; 6  *     TreeNode *left, *right; 7  *     TreeNode(int val) { 8  *         this->val = val; 9  *         this->left = this->right = NULL;10  *     }11  * }12  */13 class Solution {14 public:15     /**16      * @param root: a TreeNode, the root of the binary tree17      * @return: nothing18      */19     void flatten(TreeNode *root) {20         helper(root);21     }22     23     TreeNode* helper(TreeNode *root) {24         if (root == NULL) {25             return NULL;26         }27         if (root->left == NULL && root->right == NULL) {28             return root;29         }30         if (root->left == NULL) {31             return helper(root->right);32         }33         if (root->right == NULL) {34             root->right = root->left;35             root->left = NULL;//!important36             return helper(root->right);37         }38         //Divide39         TreeNode *leftLastNode = helper(root->left);40         TreeNode *rightLastNode = helper(root->right);41         42         //Conquer43         leftLastNode->right = root->right;44         root->right = root->left;45         root->left = NULL;//!important46         return rightLastNode;47     }48 };