ผลรวมรากถึงใบไม้ใน Python

สมมติว่าเรามีต้นไม้ไบนารีที่มีตัวเลข 0-9 เท่านั้น ทุกเส้นทางจากรากถึงใบไม้สามารถแทนจำนวนได้

ตัวอย่าง ต้นไม้เป็นดังนี้

แสดงถึงสองเส้นทางคือ 21 และ 23 ดังนั้นผลลัพธ์จะเป็น 21 + 23 = 44

ขั้นตอนการแก้ปัญหา

• สร้างฟังก์ชันเวียนเกิดชื่อ dfs() ซึ่งรับ root และ num เริ่มต้น num = 0
• ถ้าโหนดไม่ใช่ null
  • num := num * 10 + ค่าของโหนด
  • ถ้าโหนดขวาไม่ใช่ null และโหนดซ้ายไม่ใช่ null
    • sum := sum + num
    • num := num / 10
    • คืนค่าจากฟังก์ชัน
  • dfs(ขวาของโหนด, num)
  • dfs(ซ้ายของโหนด, num)
  • num := num / 10
  • คืนค่าจากเมธอด
• เริ่มต้น sum := 0
• เรียก dfs โดยใช้ root และ
• คืนค่า sum

ตัวอย่าง (Python):

ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น

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

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

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

class Solution(object): 
    def sumNumbers(self, root): 
        self.sum = 0 
        self.dfs(root) 
        return self.sum 
    
    def dfs(self, node, num=0): 
        if node: 
            num = num * 10 + node.data 
            if not node.right and not node.left: 
                self.sum += num 
                num /= 10 
                return 
            self.dfs(node.right, num) 
            self.dfs(node.left, num) 
            num /= 10 
        return 

ob1 = Solution() 
tree = make_tree([2,1,3]) 
print(ob1.sumNumbers(tree))

อินพุต

[2,1,3]

เอาต์พุต

44