資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式檢查兩棵樹是否可以透過交換節點形成
假設我們有兩棵樹，我們需要檢查是否可以透過任意次數交換任何節點的左右子樹來將第一棵樹轉換為第二棵樹。
所以，如果輸入如下所示
則輸出為 True
為了解決這個問題，我們將遵循以下步驟：
que1 := 初始值為 root0 的佇列
que2 := 初始值為 root1 的佇列
當 que1 和 que2 不為空時，執行以下操作
temp1 := 新列表，temp2 := 新列表
values1 := 新列表，values2 := 新列表
如果 que1 和 que2 包含不同數量的元素，則
返回 False
對於範圍從 0 到 que1 大小減 1 的 i，執行以下操作
將 que1[i] 的值插入到 values1 的末尾
將 que2[i] 的值插入到 values2 的末尾
如果 que1[i] 的右子節點不為空，則
將 que1[i] 的右子節點插入到 temp1 的末尾
如果 que1[i] 的左子節點不為空，則
將 que1[i] 的左子節點插入到 temp1 的末尾
如果 que2[i] 的右子節點不為空，則
將 que2[i] 的右子節點插入到 temp2 的末尾
如果 que2[i] 的左子節點不為空，則
將 que2[i] 的左子節點插入到 temp2 的末尾
如果 values1 與 values2 不相同，則
如果 values1 與 values2 的反轉順序不相同，則
返回 False
que1 := temp1，que2 := temp2
返回 True
讓我們看看以下實現，以便更好地理解：
示例
class TreeNode: def __init__(self, data, left = None, right = None): self.val = data self.left = left self.right = right class Solution: def solve(self, root0, root1): que1 = [root0] que2 = [root1] while que1 and que2: temp1 = [] temp2 = [] values1 = [] values2 = [] if len(que1) != len(que2): return False for i in range(len(que1)): values1.append(que1[i].val) values2.append(que2[i].val) if que1[i].right: temp1.append(que1[i].right) if que1[i].left: temp1.append(que1[i].left) if que2[i].right: temp2.append(que2[i].right) if que2[i].left: temp2.append(que2[i].left) if values1 != values2: if values1 != values2[::-1]: return False que1 = temp1 que2 = temp2 return True ob = Solution() root = TreeNode(2) root.right = TreeNode(4) root.right.left = TreeNode(3) root.right.right = TreeNode(5) root1 = TreeNode(2) root1.left = TreeNode(4) root1.left.left = TreeNode(3) root1.left.right = TreeNode(5) print(ob.solve(root, root1))
輸入
root = TreeNode(2) root.right = TreeNode(4) root.right.left = TreeNode(3) root.right.right = TreeNode(5) root1 = TreeNode(2) root1.left = TreeNode(4) root1.left.left = TreeNode(3) root1.left.right = TreeNode(5)
輸出
True
更新於： 2020-10-21
113 次瀏覽
廣告