Try   HackMD

Invert binary tree in O(1) space without stack/queue/recursion

contributed by < fennecJ >

昨天聽了 Jserv 開的直播–資訊科技產業專案設計 ，裡面提到了一個很有趣的問題 :
有沒有辦法不用 recursion 並 Invert binary tree in O(1) space ?( 即無法使用 stack/queue 等額外的資料結構輔助 )

要回答這個問題，我們可以先從 Morris traversal 開始看起。

Morris traversal

​核心精神 : 以 leaf node 作為回到 root 的入口

以往我們在進行 binary tree 的 traversal 時，我們之所以需要用到 recursion 或是 stack/queue 的輔助是因為我們需要有一個方法可以在進入 child node 之後，回到原本的 parent node 。

而 Morris traversal 對這個問題提供了一個解法 : 在 leaf node 的地方新增一個回到 parent 的 link ( 有的人可能會直覺聯想到 Threaded binary tree ，但兩者仍有決定性的不同， Threaded binary tree 需要在結構內額外開位子存當前 node 的 child 是否為連到 ancestor 的 thread ，而 morris 的做法則不用。 )

我們來看看他的 pseudo code (Morris traversal Inorder) ， 我參考這篇文章做了少許改編 :

  • Initialize cur as root
  • While cur != NULL
    • If the cur->left == NULL
      • a) Print cur’s data
      • b) cur = cur->right
    • Else
      • Find rightmost node in cur's left subtree which right child != cur.
      • If rightmost node's right child != NULL (it must be cur) //Which means there is a link to the cur.
        • Let rightmost node's right child = NULL //Break the link
        • Print cur's data
        • cur = cur->right.
      • Else
        • Let rightmost node's right child = cur //Build a link
        • cur = cur->left.

觀察上述 pseudo code，第一次進入 tree 的時候，由於沒有 link 存在， cur 會一直往 cur->left 走，直到到 leftmost node(cur->left == NULL) ，才藉由 link 往 parent 走，之後往 parent->right 移動。順序是 left->parent->right ，為 inOrder traversal 的順序。

以下放上熱心網友做的圖[1]幫助理解:

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
也可以看熱心網友做的動畫[2]:
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

實作程式碼 :























void morris_inOrder(node *head) {
    node *cur = head;
    while (cur) {
        node *q = cur->left;
        if (q) {
            while (q->right && q->right != cur)
                q = q->right;

            if (!q->right) {
                q->right = cur;
                cur = cur->left;
                continue;
            }
            q->right = NULL;
            printf("%d ", cur->data);
            cur = cur->right;
            continue;
        }
        printf("%d ", cur->data);
        cur = cur->right;
    }
}

空間複雜度 : O(1)
時間複雜度 : O(2n) ，因為每個 node 最多只會經過兩次
事實上，只要在將第 15 行的

printf("%d ", cur->data);

移到第 10 行後面
就可以將其改為 preOrder：























void morris_preOrder(node *head) {
    node *cur = head;
    while (cur) {
        node *q = cur->left;
        if (q) {
            while (q->right && q->right != cur)
                q = q->right;

            if (!q->right) {
                q->right = cur;
                printf("%d ", cur->data);
                cur = cur->left;
                continue;
            }
            q->right = NULL;
            cur = cur->right;
            continue;
        }
        printf("%d ", cur->data);
        cur = cur->right;
    }
}

至於 postOrder ，若要用 morris alg 實作，會稍微複雜一些，這裡暫不討論，有興趣的人可以參考這篇

接下來我們回來看看題目。

Invert binary tree in O(1) space

以 inOrder 或是 preOrder 順序對 tree 進行 invert，若在當前 node 的所有 children 尚未遍歷之前就發生 invert 則會導致原本 left -> root -> right 順序變成 left -> root -> left( 因為 root invert 後原本的 left 和 right child 會互換 ) 這樣 cur 究竟要往左或往右走不太好處理。
我們要確保對一 node invert 之前其所有 children 都遍歷過了。
在 morris traversal 的基礎上進行改編，得到以下程式碼 ( 由 此篇文章 改編 )




























void invert_bin_tree(node *root) {
    node *cur = new_node(0);
    cur->left = root;
    while (cur) {
        node *q = cur->left;
        if (q) {
            while (q->right && q->right != cur)
                q = q->right;
            if (!q->right) {
                q->right = cur;
                cur = cur->left;
                continue;
            }
            node *tmp = cur->left;
            while (tmp) {
                swap(&tmp->left, &tmp->right);
                if (tmp == q)
                    break;
                tmp = tmp->left;
            }
            q->left = NULL;
	    /* Link from q to cur is changed from q->right into q->left,
	       causing by while loop for tmp in line 15. */
        }
        cur = cur->right;
    }
}

不同的地方有幾個點:

  • 多了一個 dummy node 指向 root
  • 第 12 行原本 break link 應為 q->right = NULL; 被改為 q->left = NULL;

之所以多了一個 dummy node 並指向 root ，是為了讓 cur 走到 right most node 時，能藉這個 node 走回 root，並對 root 進行 invert 。
而為何從 q->right = NULL; 改為 q->left = NULL;
是因為在前面的 while(tmp) 中， 會對 tmp 的 left child 以及 right child 進行交換，直到 tmp == q 為止進行最後一次交換。
此時 q 的 left 和 right child 進行交換，導致原本指向 cur 的 right child 變成 left child ，因此要打破這個 link 要用 q->left = NULL; 我嘗試做了一個動畫幫助理解 :
可以在這裡一頁一頁翻

那麼，有沒有辦法可以不額外新增一個 dummy node 呢 ?
近日我在 leetcode 討論區看到 這個解答

正如前面所提，如果用原本的 morris_alg 來做的話，難點在於判斷 cur 何時該往左走，何時該往右走，因此關鍵在於，如何判斷進入一個 node 前該 subtree 已經被翻轉過了 ( 即該 node 的 parent 已經被翻轉過了 )。如果被翻轉過了，那就用翻轉後的方法進行 morris alg ( left 和 right 互換 ) ，否則就照沒翻轉的情形進行 morris alg 。 我們將原本的 morris_inOrder left right 互換，但是仍維持從 cur 的 left subtree 開始處理，因此 q 的 init value 維持 cur->left























void swap_LR_morris_inOrder(node *head) {
    node *cur = head;
    while (cur) {
        node *q = cur->left;
        if (q) {
            while (q->left && q->left != cur)
                q = q->left;

            if (!q->left) {
                q->left = cur;
                cur = cur->right;
                continue;
            }
            q->left = NULL;
            swap(&cur->left, &cur->right);
            cur = cur->left;
            continue;
        }
        swap(&cur->left, &cur->right);
        cur = cur->left;
    }
}

接著在改編後的基礎上加回未翻轉的 morris_alg ，用以下 code 取代原本第 9 行的 if (!q->left) block 的內容









q = cur->left;	// 回到原本 morris_alg 的起點
while (q->right && q->right != cur)
    q = q->right;
if (!q->right) {
    q->right = cur;
    cur = cur->left;
    continue;
}

最後我們就得到了以下 code :




























void invert_bin_tree(node *head) {
    node *cur = head;
    while (cur) {
        node *q = cur->left;
        if (q) {
            while (q->left && q->left != cur)
                q = q->left;

            if (!q->left) {
                q = cur->left; // 回到原本 morris_alg 的起點
                while (q->right && q->right != cur)
                    q = q->right;
                if (!q->right) {
                    q->right = cur;
                    cur = cur->left;
                    continue;
                }
            }
            q->left = NULL;
            swap(&cur->left, &cur->right);
            cur = cur->left;
            continue;
        }
        swap(&cur->left, &cur->right);
        cur = cur->left;
    }
}

再來我們對上面的 code 進行簡化，初步觀察可以發現第 20~22 行是多餘的，把他刪掉，變成 :

























void invert_bin_tree(node *head) {
    node *cur = head;
    while (cur) {
        node *q = cur->left;
        if (q) {
            while (q->left && q->left != cur)
                q = q->left;

            if (!q->left) {
                q = cur->left; // 回到原本 morris_alg 的起點
                while (q->right && q->right != cur)
                    q = q->right;
                if (!q->right) {
                    q->right = cur;
                    cur = cur->left;
                    continue;
                }
            }
            q->left = NULL;
        }
        swap(&cur->left, &cur->right);
        cur = cur->left;
    }
}

接下來我們開始檢視上面的 code 究竟做了什麼 ?
首先一樣從 cur 的 left subtree 開始進行 (node *q = cur->left;)
再來是如何判斷進入 cur 之前已經發生了翻轉，由於我們建立 link 時只會從 leaf node 的 right child 連，因此若在 cur 的 children 中存在 node 的 left child 能連回 cur 的話表示這個 node( 作為 cur 的 parent) 已經被翻轉過了。第 9 行的 if (!q->left) 就是用來判斷是否有發生翻轉的條件。
另外，若存在符合以上描述的 node ，此 node 必為 subtree 中的 leftmost node ，因為 cur 第一次進入一個 subtree 時必會一直走到 leftmost node ，之後再藉 link 往回走 ( 第一次進入時狀態為未翻轉，會一直執行第 15 行，往 cur->left 移動 ) 。
可觀察以下動畫幫助理解 :

也可在 這裡 一頁一頁翻

基本上以上就是以 morris_alg 進行 invert bin tree 而不用到 dummy node 的做法。
最後， cur 走回 parent 唯一的路徑只有在 swap 後第 22 行的 cur = cur->left; ，因此只要進入 !q->left 的區塊，表示目前是 cur 第一次進入該 subtree ，不會事先有 link 存在，第 11 行的 && q->right != cur 以及第 13 行的 if (!q->right) 是可以直接拔掉的。























void invert_bin_tree3(node *root) {
    node *cur = root;
    while (cur) {
        node *q = cur->left;
        if (q) {
            while (q->left && q->left != cur)
                q = q->left;
            if (!q->left) {
                q = cur->left;
                while (q->right)
                    q = q->right;

                q->right = cur;
                cur = cur->left;
                continue;
            }
            q->left = NULL;
        }
        swap(&cur->right, &cur->left);
        cur = cur->left;
    }
}

以上 code 皆可到 我的 Github 上下載，最後附上 LeetCode 226. 的解答 :







































/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

inline void swap(struct TreeNode  **a, struct TreeNode  **b) {
    struct TreeNode  *tmp = *a;
    *a = *b;
    *b = tmp;
}

struct TreeNode* invertTree(struct TreeNode* root){
    struct TreeNode *cur = root;
    while (cur) {
        struct TreeNode *q = cur->left;
        if (q) {
            while (q->left && q->left != cur)
                q = q->left;
            if (!q->left) {
                q = cur->left;
                while (q->right)
                    q = q->right;
                
                q->right = cur;
                cur = cur->left;
                continue;
            }
            q->left = NULL;
        }
        swap(&cur->left, &cur->right);
        cur = cur->left;
    }
    return root;
}

參考資料

  1. Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间） ↩︎

  2. Explain Morris inorder tree traversal without using stacks or recursion ↩︎

Last changed by 
 
fennecJ
0
2
2197

Read more

2024q1 Homework1 (lab0)

contributed by &lt; fennecJ &gt;

Jul 3, 2024
2024q1 Homework2 (quiz1+2)

contributed by &lt; fennecJ &gt;

Jul 1, 2024
2024q1 Homework5 (assessment)

作者嘗試用他的專業解決真實世界發生的問題，並將過程遇到的困難和啟發記錄下來。其中，我印象較深刻的部份有幾點：

Jun 30, 2024
FPGA Final - quantized single head attention accelerator on pynq-z2

本次期末專題的題目為嘗試在 pynq-z2 上實做出簡單的 single head attentation 的運算加速器。

Jul 1, 2023
Read more from fennecJ
Published on HackMD