題目出處

114. Flatten Binary Tree to Linked List

難度

medium

個人範例程式碼 – iterative 解

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root:
            return 

        stack = deque([root])

        while stack:
            node = stack.pop()
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)


            node.right = stack[-1] if stack else None # prev node -> current node
            node.left = None

        return

算法說明

個人覺得很酷的一題，直接把 Tree 改成 Linked List，考了非常多資料結構的操作。

把前一個 node 連結至 stack[-1] 的位置。

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

input handling

當沒有 root 時，直接回傳

Boundary conditions

搜尋至 None 時，return

個人範例程式碼 – recursive 解

class Solution:
    """
    @param root: a TreeNode, the root of the binary tree
    @return: nothing
    """
    def flatten(self, root: TreeNode):
        # write your code here
        if not root:
            return

        self.prev = None
        self.dfs(root)
        return 

    def dfs(self, root):
        if not root:
            return 

        if self.prev is not None:
            self.prev.left = None
            self.prev.right = root

        self.prev = root
        tmp_right = root.right
        self.dfs(root.left)
        self.dfs(tmp_right) # root.right 回到此處時已經被修改

算法說明

這做法要注意的是，因為我們是 in-place 的改 node right，
在 dfs 回來之後已經不是原來我們預期的那個 node.right，因此要先事前拷貝一份。

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

input handling

當沒有 root 時，直接回傳

Boundary conditions

搜尋至 None 時，return

個人範例程式碼 – recursive 解 (使用 global 變數，個人覺得比較不直覺一點)

class Solution:
    """
    @param root: a TreeNode, the root of the binary tree
    @return: nothing
    """
    def flatten(self, root: TreeNode):
        # write your code here
        if not root:
            return

        self.prev = None
        self.dfs(root)
        return 

    def dfs(self, root):
        if not root:
            return 

        # divide
        self.dfs(root.right)
        self.dfs(root.left)

        # conquer  right -> prev(deeper node)
        root.right = self.prev
        root.left = None
        self.prev = root

算法說明

這個方法使用了 class 的 global 變數，使用好不好見仁見智，
但邏輯清楚一些，每次都記錄前一個 node 作為 prev，並把 current node 連結 prev node。

這裡有個比較不直覺的地方，prev node 紀錄的是「相對比較底層的」node，
因此是用 return 過程時的路徑 node.right 去連接 prev (這部分概念有點跟 prev 實質意義上顛倒)

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

input handling

當沒有 root 時，直接回傳

Boundary conditions

搜尋至 None 時，return

Reference

• 453 · Flatten Binary Tree to Linked List