Re: [閒聊] 每日leetcode

[CP3isgood (夜空メル的かぷ民)]

951. Flip Equivalent Binary Trees

思路:
翻轉後父點的兩個子點不變
做兩次BFS
第一次紀錄tree1每個點的子點
第二次檢查tree2是否相同


func flipEquiv(root1 *TreeNode, root2 *TreeNode) bool {
    if root1 == nil && root2 == nil {
        return true
    } else if root1 == nil || root2 == nil {
        return false
    }

    rec := map[int][]int{}

    queue1 := []*TreeNode{root1}
    for len(queue1) > 0 {
        n := len(queue1)
        for i := 0; i < n; i++ {
            node := queue1[0]
            queue1 = queue1[1:]
            if node.Left != nil {
                queue1 = append(queue1, node.Left)
                rec[node.Val] = append(rec[node.Val], node.Left.Val)
            }
            if node.Right != nil {
                queue1 = append(queue1, node.Right)
                rec[node.Val] = append(rec[node.Val], node.Right.Val)
            }
        }
    }

    queue2 := []*TreeNode{root2}
    for len(queue2) > 0 {
        n := len(queue2)
        for i := 0; i < n; i++ {
            node := queue2[0]
            queue2 = queue2[1:]
            if node.Left != nil && node.Right != nil {
                if len(rec[node.Val]) != 2 || !check(rec[node.Val], node.Left.Val) || !check(rec[node.Val], node.Right.Val) {
                    return false
                }
                queue2 = append(queue2, node.Left, node.Right)
            } else if node.Left != nil {
                if len(rec[node.Val]) != 1 || !check(rec[node.Val], node.Left.Val) {
                    return false
                }
                queue2 = append(queue2, node.Left)
            } else if node.Right != nil {
                if len(rec[node.Val]) != 1 || !check(rec[node.Val], node.Right.Val) {
                    return false
                }
                queue2 = append(queue2, node.Right)
            } else if len(rec[node.Val]) != 0 {
                return false
            }
        }
    }
    return true
}

func check(rec []int, target int) bool {
    for _, i := range rec {
        if i == target {
            return true
        }
    }
    return false
}

=====

寫完看別人的答案發現三五行就解決了

直接一次DFS比較就好

我這輩子就這樣了

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.184.173 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729764044.A.98D.html
※ 編輯: CP3isgood (36.227.184.173 臺灣), 10/24/2024 18:02:33
→ DJYOMIYAHINA: 怎麼那麼常 我今天不寫了