• 由於都是LeetCode的題目，就直接在該網站上驗證
• 以下演算法直接貼到LeetCode都可以運作

# ​​#3LeetCode

• Recursive
• idea:
• 同個parent的children，左邊比右邊優先
• divide and conquer
`​​struct TreeNode *_flatten(struct TreeNode * node)`
`​​ {`
`​​  if (node == NULL) {`
`​​    return NULL;`
`​​  }`
`​​  if (node->right) {`
`​​    node->right = _flatten(node->right);`
`​​  }`
`​​  if (node->left) {`
`​​    struct TreeNode *tmp = node->right;`
`​​    node->right = _flatten(node->left);`
`​​    struct TreeNode *t = node->right;`
`​​    while (t->right) {`
`​​      t = t->right;`
`​​    }`
`​​    t->right = tmp;`
`​​    node->left = NULL;`
`​​  }`
`​​  return node;`
`​​}`
`​​void flatten(struct TreeNode* node) {`
`​​    _flatten(node);`
`​​}`

• Non-Recursive
• idea:
• 不斷的讓左子樹移動到右子樹，讓原先的右子樹長到移動後的左子樹的右子樹
`​​void flatten(struct TreeNode* root) {`
`​​    struct TreeNode* leftt;`
`​​    while(root!=NULL){`
`​​        if(root->left!=NULL){`
`​​            leftt=root->left;`
`​​            while(leftt->right!=NULL) leftt=leftt->right;`
`​​            leftt->right=root->right;`
`​​            root->right=root->left;`
`​​            root->left=NULL;`