【二叉树】叶子相似的树
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
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
二维码