題目1 . 葉子相似的樹
題目描述：
image.png
題目分析
第一個版本 遞歸遍歷
很清楚了 要想判斷 是否相似 必須知道 全部的葉子節(jié)點
因為是有順序的采用中順遍歷(dfs)
6 5 7 2 4 3 9 1 8
二叉樹遍歷的遞歸實現(xiàn)娱局，每個結(jié)點只需遍歷一次仿野，故時間復(fù)雜度為O(n)恋谭。
而使用了遞歸，最差情況下遞歸調(diào)用的深度為O(n)，所以空間復(fù)雜度為O(n)翔忽。
缺點：必須全部遍歷完畢 才能獲取葉子節(jié)點
如何獲取第一個葉子節(jié)點 ？
第二個版本 非遞歸遍歷
利用棧的特性（后進先出） 完成中順遍歷 先遍歷完畢全部左面的然后遍歷右邊的
注意 這里不是隊列 隊列是層次遍歷 層次遍歷不滿足葉子節(jié)點輸出順序
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)
//檢查結(jié)果
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)
//只輸出葉子節(jié)點
if root.Left == nil && root.Right == nil {
*array = append(*array, root.Val)
}
inorder(root.Right, array)
}
image.png
下個題目：
validate-binary-search-tree
image.png
