0x00 題目
請考慮一棵二叉樹上所有的葉子
這些葉子的值按 從左到右 的順序排列形成一個 葉值序列
如果有兩棵二叉樹的葉值序列是相同
那么我們就認為它們是 葉相似 的
如果給定的兩個頭結點分別為 root1 和 root2 的樹
是葉相似的，則回傳 true；否則回傳 false
0x01 思路
先獲取 root1 的 葉值序列
再獲取 root2 的 葉值序列
依次比較 值 是否相等即可
0x02 解法
語言：Swift
樹節點：TreeNode
public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init() { self.val = 0; self.left = nil; self.right = nil; }
public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
self.val = val
self.left = left
self.right = right
}
}
解法：
func leafSimilar(_ root1: TreeNode?, _ root2: TreeNode?) -> Bool {
// 存放 root1 的葉子值
var arr1: [Int] = []
// 存放 root2 的葉子值
var arr2: [Int] = []
// 獲取所有的葉子值
func find(_ t: TreeNode?) -> [Int] {
guard let t = t else { return [] }
var res: [Int] = []
// 左右節點都為空時，是葉子節點
if t.left == nil && t.right == nil {
return [t.val]
}
// 依次遞回左右節點
let res1 = find(t.left)
let res2 = find(t.right)
// 合并左右子樹的結果
res.append(contentsOf: res1)
res.append(contentsOf: res2)
return res
}
arr1 = find(root1)
arr2 = find(root2)
// 兩個陣列的元素都相等
if arr1.elementsEqual(arr2) {
return true
}
return false
}
學習五筆
五筆小程式：XWubi
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/388394.html
標籤：其他
上一篇：Android開發環境的配置流程
下一篇：如何更準確地檢測帶圓角的矩形