993. Кузены в двоичном дереве

Stanislav Gumeniuk включен в Leetcode Leetcode-Problem

2024-02-04 353 слов 2 минуты

Содержание

Автоматический перевод

Эта статья переведена автоматически с английский на русский. Оригинал доступен на английский.

Решение задачи 993 “Cousins in Binary Tree” (Кузены в двоичном дереве) с LeetCode.

Задача

Дан корень двоичного дерева с уникальными значениями и значения двух различных узлов дерева x и y. Верните true, если узлы, соответствующие значениям x и y в дереве, являются кузенами, или false в противном случае.

Два узла двоичного дерева являются кузенами, если они имеют одинаковую глубину с разными родителями.

Обратите внимание, что в двоичном дереве корневой узел находится на глубине 0, а дети каждого узла на глубине k находятся на глубине k + 1.

Пример 1:

Вход: root = [1,2,3,4], x = 4, y = 3 Выход: false

Пример 2:

Вход: root = [1,2,3,null,4,null,5], x = 5, y = 4 Выход: true

Пример 3:

Вход: root = [1,2,3,null,4], x = 2, y = 3 Выход: false

Примечания:

Количество узлов в дереве находится в диапазоне [2, 100]. 1 <= Node.val <= 100 Каждый узел имеет уникальное значение. x != y x и y существуют в дереве.

Решение

Поиск в ширину (BFS)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isCousins(root *TreeNode, x int, y int) bool {
    q := [][]*TreeNode{}

    if root == nil {
        return true
    }
    if root.Left!=nil && root.Right!=nil {
        if (root.Left.Val == x || root.Left.Val == y) &&
        (root.Right.Val == x || root.Right.Val == y) {
            return false
        }
    }
    q = append(q, []*TreeNode{root.Left, root.Right})
    for k:=0;k<len(q); {
        d := []*TreeNode{}
        c:=0

        for idx:=range q[len(q)-1] {
            if q[len(q)-1][idx] == nil {
                continue
            }
            if (q[len(q)-1][idx].Val == x) ||  (q[len(q)-1][idx].Val == y){
                c++
            }
            if c == 2 {
                return true
            }
            r := q[len(q)-1][idx]
            if (r.Left != nil && r.Right!= nil) {
                if (r.Left.Val == x || r.Left.Val == y) &&
                    (r.Right.Val == x || r.Right.Val == y) {
                        return false
                }
            }

            if q[len(q)-1][idx].Left != nil {
                d = append(d,q[len(q)-1][idx].Left)
            }
            if q[len(q)-1][idx].Right != nil {
                d = append(d,q[len(q)-1][idx].Right)
            }
        }

        if len(d)>0 {
            q = append(q, d)
        }
        k++

    }
    return false
}