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 tree 17 * @return: nothing 18 */ 19 void flatten(TreeNode *root) { 20 if(!root) return; 21 vector<TreeNode*> allNodes; 22 preorder(root, allNodes); 23 int n = allNodes.size(); 24 for(int i=0; i<n-1; i++) { 25 allNodes[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<TreeNode*> &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 tree 17 * @return: nothing 18 */ 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;//!important 36 return helper(root->right); 37 } 38 //Divide 39 TreeNode *leftLastNode = helper(root->left); 40 TreeNode *rightLastNode = helper(root->right); 41 42 //Conquer 43 leftLastNode->right = root->right; 44 root->right = root->left; 45 root->left = NULL;//!important 46 return rightLastNode; 47 } 48 };