题目1 . 叶子相似的树
题目描述：
image.png
题目分析
第一个版本 递归遍历
很清楚了 要想判断 是否相似 必须知道 全部的叶子节点
因为是有顺序的采用中顺遍历(dfs)
6 5 7 2 4 3 9 1 8
二叉树遍历的递归实现，每个结点只需遍历一次，故时间复杂度为O(n)。
而使用了递归，最差情况下递归调用的深度为O(n)，所以空间复杂度为O(n)。
缺点：必须全部遍历完毕 才能获取叶子节点
如何获取第一个叶子节点 ？
第二个版本 非递归遍历
利用栈的特性（后进先出） 完成中顺遍历 先遍历完毕全部左面的然后遍历右边的
注意 这里不是队列 队列是层次遍历 层次遍历不满足叶子节点输出顺序
image.png
code
/**
https://leetcode-cn.com/submissions/detail/7688864/
**/
func leafSimilar(root1 *TreeNode, root2 *TreeNode) bool {
var array1, array2 []int
inorder(root1, &array1)
inorder(root2, &array2)
//检查结果
if len(array1) != len(array2) {
return false
}
for i := 0; i < len(array1); i++ {
if array1[i] != array2[i] {
return false
}
}
return true
}
/**
Golang的引用类型包括 slice(大小固定)、map 和 channel
**/
func inorder(root *TreeNode, array *[]int) {
if root == nil {
return
}
inorder(root.Left, array)
//只输出叶子节点
if root.Left == nil && root.Right == nil {
*array = append(*array, root.Val)
}
inorder(root.Right, array)
}
image.png
下个题目：
validate-binary-search-tree
image.png
