動機

剛好看到，紀錄一下

delete

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
            return root
        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
            return root
        else:
            if not root.left and not root.right:
                return None
            elif not root.left:
                return root.right
            elif not root.right:
                return root.left
            else:
                # find min in root.right
                now = root.right
                prev = root
                while now.left:
                    prev, now = now, now.left
                
                if now == root.right: # no left
                    now.left = root.left
                else:
                    prev.left = now.right
                    now.left = root.left
                    now.right = root.right
                return now

threading binary tree

不用遞迴與stack完成inorder走訪，雖然說放這裡感覺與bst無關，不過我暫時想不到放哪就先這樣

就是在inorder走訪時，想像像linked list一樣，有一個prev，之後就是開始連接，修prev與現在的node 左邊指回去，右邊指回來 (其實要反過來應該也可以)

中序

class Node:
  def __init__(self):
    self.is_left = self.is_right = True
    self.left = self.right = None

def threading(root,prev = None):
  if root is None:
    return
  else:
    threading(root.left, prev)

    # left 指回去
    if root.left is None:
      root.is_left = False
      root.left = prev
    # right 指回來，變成一個圈
    if prev is not None:
      prev.is_right = False
      prev.right = root
    
    threading(root.right, root)

前序

def pre(root,prev):
    if root:
        originRight = root.right
        pro = pre(root.left, root)
        ret = pre(originRight, pro)
        if prev:
            prev.left, prev.right = None, root
        # 目前最大的node
        if not pro and not ret:
            return root
        elif not pro or not ret:
            return [x for x in [pro,ret] if x][0]
        else:
            return ret
    else:
        return None
pre(root, None)