→ Rushia: 大師 02/29 18:50
推 DJYOSHITAKA: 100 大濕 02/29 18:58
推 JerryChungYC: 我沒超過5天 我好爛 02/29 19:03
→ NCKUEECS: 大師 看到跟你一樣這麼多if我就放心了 02/29 19:03
每日連續解100天了，有點累
之後可能不會每天都解
1609. Even Odd Tree
給你一棵二元樹，請問是不是Even Odd Tree
Even Odd Tree要滿足下面三個條件
1.root的level index為1，他的children level index為2，以此類推
2.所有level index是偶數的node，值必須是奇數，且從左到右要嚴格遞增
3.所有level index是奇數的node，值必須是偶數，且從左到右必須是嚴格遞減
思路：
用BFS去檢視每一層是否滿足條件
golanf code:
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isEvenOddTree(root *TreeNode) bool {
queue := []*TreeNode{}
queue = append(queue, root)
cnt := 1
level := 0
for len(queue) > 0 {
for cnt > 1 {
temp := queue[0]
queue = queue[1:]
if level%2 == 0 {
if temp.Val >= queue[0].Val || temp.Val%2 != 1 {
return false
}
} else {
if temp.Val <= queue[0].Val || temp.Val%2 != 0 {
return false
}
}
if temp.Left != nil {
queue = append(queue, temp.Left)
}
if temp.Right != nil {
queue = append(queue, temp.Right)
}
cnt--
}
if level%2 == 0 {
if queue[0].Val%2 != 1 {
return false
}
} else {
if queue[0].Val%2 != 0 {
return false
}
}
if queue[0].Left != nil {
queue = append(queue, queue[0].Left)
}
if queue[0].Right != nil {
queue = append(queue, queue[0].Right)
}
queue = queue[1:]
level++
cnt = len(queue)
}
return true
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.133.158 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1709203693.A.BFB.html