โปรแกรมเปลี่ยน Root ของ Binary Tree ให้เป็น Leaf Node ด้วย Python

โจทย์: กำหนด leaf node ให้กลายเป็น root ใหม่ โดยกฎ: left child กลายเป็น right child, parent กลายเป็น left child (และ parent เก่าตัด link ไปยัง node นั้น) ใช้ recursion ย้อนกลับจาก leaf ไป root เดิม

อัลกอริทึม

1. ฟังก์ชัน helper(node, new_parent) รับโหนดปัจจุบันและ parent ใหม่
2. ถ้า node เป็น root เดิม: ตั้ง parent, ตัด link left/right ที่ชี้ไป new_parent, คืน root
3. ถ้ามี left child: ย้าย left ไป right
4. ตัด link parent เก่าที่ชี้มาหา node
5. Recursive: node.left = helper(node.parent, node)
6. ตั้ง node.parent = new_parent, คืน node

ตัวอย่างโค้ด

import collections

class TreeNode:
    def __init__(self, data, left=None, right=None, parent=None):
        self.data = data
        self.left = left
        self.right = right
        self.parent = parent

def insert(temp, data):
    que = [temp]
    while que:
        temp = que.pop(0)
        if not temp.left:
            temp.left = TreeNode(data, parent=temp) if data is not None else TreeNode(0, parent=temp)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            temp.right = TreeNode(data, parent=temp) if data is not None else TreeNode(0, parent=temp)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree

def search_node(root, element):
    if root is None: return None
    if root.data == element: return root
    res1 = search_node(root.left, element)
    if res1: return res1
    return search_node(root.right, element)

def solve(root, leaf):
    def helper(node, new_par):
        if node == root:
            node.parent = new_par
            if node.left == new_par: node.left = None
            if node.right == new_par: node.right = None
            return root
        if node.left:
            node.right = node.left
        if node.parent.left == node:
            node.parent.left = None
        node.left = helper(node.parent, node)
        node.parent = new_par
        return node
    return helper(leaf, None)

root = make_tree([5, 3, 7, 2, 4, 6, 8])
root = solve(root, search_node(root, 8))

def print_tree(root):
    if root:
        print_tree(root.left)
        print(root.data, end=', ')
        print_tree(root.right)

print_tree(root)  # Output: 2, 3, 4, 5, 7, 6, 8,

อินพุต/เอาต์พุต

Input: root=make_tree([5,3,7,2,4,6,8]), leaf=8
Output (inorder): 2, 3, 4, 5, 7, 6, 8,