DAY31 Flatten Binary Tree to Linked List

第 11 屆 iThome 鐵人賽

自我挑戰組

刷題記錄與人生分享系列第 31 篇

11th鐵人賽 leetcode c javascript

keyhouse12

2019-10-02 08:41:36

1019 瀏覽

分享至

題目:

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
!

解題思路:

我個人認為非遞迴比遞迴解法還更好理解，先把左節點移置右節點後把根節點往右節點移動，以此循環值到條件不符合為止。

圖片來源: https://www.cnblogs.com/grandyang/p/4293853.html

C版本:

void flatten(struct TreeNode* root) {
    while(root != NULL) {  
            if(root->left != NULL) {  
                struct TreeNode* ptr = root->left;  
                while(ptr->right != NULL) 
                    ptr = ptr->right;  
                ptr->right = root->right;  
                root->right = root->left;  
                root->left = NULL;  
            }  
            root = root->right;  
        }  
}

Javascript版本:

while(root != null) {  
   if(root.left != null) {  
      var ptr = root.left
      while(ptr.right != null) 
        ptr = ptr.right;  
        ptr.right = root.right;  
        root.right = root.left;  
        root.left = null;  
      }  
      root = root.right;  
}