Convert

114 Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

def flatten(self, root: TreeNode) -> None:
    self.preNode = None
    
    def helper(node):
        nonlocal preNode
        if not node: return None
        helper(node.right)
        helper(node.left)
        
        node.right = preNode
        node.left = None
        preNode = node
        
    helper(root)

def flatten(self, root: TreeNode) -> None:
    if not root: return
    
    node = root
    
    while node:
        if node.left: 
            rightMost = node.left

            while rightMost.right:
                rightMost = rightMost.right
            
            rightMost.right = node.right
            node.right = node.left
            node.left = None
            
        node = node.right
        

106t Convert Sorted LinkedList to Balanced BST

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

• Divide and Conquer

public TreeNode sortedListToBST(ListNode head) {
    if (head == null){
        return null;
    }
    return BSTHelper(head, null);
}

public TreeNode BSTHelper(ListNode head, ListNode tail) {
    if (head == tail){
        return null;
    }

    // let slow goes to middle point
    ListNode slow = head, fast = head;
    while(fast.next != tail && fast.next.next != tail){
        slow = slow.next;
        fast = fast.next.next;
    }
    TreeNode left = BSTHelper(head, slow);
    TreeNode right = BSTHelper(slow.next, tail);

    TreeNode root = new TreeNode(slow.val);
    root.left = left;
    root.right = right;
    return root;
}

426 Convert BST to double linked list

Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.並且首尾相連

private Node pre;
public Node treeToDoublyList(Node root) {
    if(root == null) return null;

    Node dummy = new Node(0);
    pre = dummy;
    helper(root);

    // now the "pre" is the tail node
    // connect head and tail
    pre.right = dummy.right;
    dummy.right.left = pre;

    return dummy.right;
}

private void helper(Node node){
    if(node == null) return;
    helper(node.left);
    pre.right = node; // 同時將dummy.right 指向 head node
    node.left = pre;
    pre = node; // 這裏dummy 不跟著變化
    helper(node.right);
}

"""
inorder traverse
current node and tail node 之間更新
需要兩個pointer紀錄head and tail
最後head and tail連起來
"""
class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root: return None
        self.head, self.tail = None, None
        self.helper(root)
        self.tail.right = self.head
        self.head.left = self.tail
        return self.head
      
    def helper(self, node):
        if not node: return
        
        self.helper(node.left)
        
        if self.tail:
            self.tail.right = node
            node.left = self.tail
        else:
            # 只會更新一次, 在head的時候
            self.head = node
        self.tail = node
        self.helper(node.right)