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

#3    LeetCode

演算法
reference
  • 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;