資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式檢查兩棵樹的葉子序列是否相同
假設我們有兩棵二叉樹，我們需要檢查這兩棵樹中從左到右的葉子序列是否相同。
因此，如果輸入類似於
則輸出將為True，因為兩棵樹的序列都是[2, 6]。
為了解決這個問題，我們將遵循以下步驟
- c := 一個新的列表
- 定義一個函式inorder()。它將接收根節點和c作為引數。
- 如果c為空，則
- c := 一個新的列表
- 如果根節點不為空，則
- inorder(根節點的左子節點, c)
- 如果根節點的左子節點和右子節點都為空，則
- 將根節點的值插入到c的末尾
- inorder(根節點的右子節點, c)
- 返回c
- 從主方法中執行以下操作
- 如果inorder(root0)與inorder(root1)相同，則
- 返回True
- 否則，
- 返回False
讓我們檢視以下實現以更好地理解
示例
class TreeNode: def __init__(self, data, left = None, right = None): self.val = data self.left = left self.right = right class Solution: c = [] def inorder(self, root, c=None): if c is None: c = [] if root: self.inorder(root.left, c) if not root.left and not root.right: c.append(root.val) self.inorder(root.right, c) return c def solve(self, root0, root1): if self.inorder(root0) == self.inorder(root1): return True else: return False ob = Solution() root1 = TreeNode(1) root1.right = TreeNode(3) root1.right.left = TreeNode(2) root1.right.right = TreeNode(6) root2 = TreeNode(1) root2.left = TreeNode(3) root2.right = TreeNode(6) root2.left.left = TreeNode(2) print(ob.solve(root1, root2))
輸入
root1 = TreeNode(1) root1.right = TreeNode(3)root1.right.left = TreeNode(2)
root1.right.right = TreeNode(6)
root2 = TreeNode(1)
root2.left = TreeNode(3)
root2.right = TreeNode(6)root2.left.left = TreeNode(2)
輸出
True
更新於: 2020年11月26日
83 次檢視
廣告