題目

解題概念

  • 此題簡單來說，就是給定一棵二元樹 root，透過 Pre-order Traversal (前序追蹤)的方式，將其轉變成類似 Linked List 的結構
  • 由於此題要求要直接在 root 上做處理，故有以下兩大重點要注意 :
    1. 依照前序去改變二元樹結構

    2. 在改變結構時，會需要另外用函數找到 root 左子樹的最右下節點 rightMOST，因為需要將 rightMOST 的右子樹設為原 root 的右子樹 (即 root.right )

實際寫Code

  • 目標函式 : flatten(root)
    • 節點格式 : 
      1
      2
      3
      4
      5
      class TreeNode(object):
          def __init__(self, val=0, left=None, right=None):
              self.val = val
              self.left = left
              self.right = right
    • Input : root: TreeNode
    • Output : None Do not return anything, modify root in-place instead.
  • 前置作業 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    # 若為空樹，則直接結束
    if root == None:
        return

    nextright = TreeNode() # 儲存原本 root 的右子樹
    rightMOST = TreeNode() # 儲存原本 root 左子樹的最右下節點

    # 尋找出 node 的最右下節點    
    def rightmost(node):

        # 若已經無法再往右下搜尋，則此點即為 rightMOST
        if node.right == None:
            return node

        # 否則繼續往右下搜尋
        return rightmost(node.right)
  • 主要迴圈 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    # 若 root 尚未為空
    while root != None :

        # 若 root 有左子樹
        if root.left != None :
            
            # 找出左子樹的 rightMOST
            rightMOST = rightmost(root.left)

            # 存好原本 root 的右子樹
            nextright = root.right

            # 將左子樹移至右子樹
            root.right = root.left

            # 左子樹設為空
            root.left = None

            # 將原本 root 的右子樹接回 rightMOST 之後
            rightMOST.right = nextright
                
        # 最後移至下一個節點
        root = root.right