Question

Я пытался решить эту проблему в Leetcode.

Проблема заключается в следующем:

Для двоичного дерева T мы можем определить бросок выполните следующие действия: выберите любой узел и поменяйте местами левые и правые дочерние поддеревья.

Двоичное дерево X является флип-эквивалентом двоичного дерева Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого числа операции переворачивания.

Напишите функцию, которая определяет, являются ли два двоичных дерева эквивалентными при перевороте. Деревья задаются root узлами root1 и root2.

Вы можете обратиться к ссылке для примера.

Итак, для этой проблемы я попробовал следующее.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
        Map<TreeNode,TreeNode> a1 = new HashMap<>();
        Map<TreeNode,TreeNode> a2 = new HashMap<>();
        if(root1!=null){
            q1.add(root1);
            a1.put(root1,null);
        }
        if(root2!=null){
            q2.add(root2);
            a2.put(root2,null);
        }

        while(!q1.isEmpty() && !q2.isEmpty()){
            TreeNode node1 = q1.poll();
            TreeNode node2 = q2.poll();

            // System.out.println(node1.val +" "+node2.val+" ");

            if(node1.val!=node2.val){
                return false;
            }

            if(a1.get(node1)==null){
                if(a2.get(node2)!=null){
                    return false;
                }
            }else{
                if(a2.get(node2)==null){
                    return false;
                }
                // System.out.println(node1.val +" "+node2.val+" "+a1.get(node1).val+" "+a2.get(node2).val+" "+node1+" "+node2);
                if(a1.get(node1).val!=a2.get(node2).val){
                    return false;
                }
            }

            // System.out.println(node1+" "+node2);

            if(node1.left==null && node2.left==null){
                if(node1.right==null && node2.right!=null){
                    return false;
                }else if(node1.right!=null && node2.right==null){
                    return false;
                }else if(node1.right!=null && node2.right!=null){
                    if(node1.right.val!=node2.right.val){
                        return false;
                    }else{
                        q1.add(node1.right);
                        a1.put(node1.right,node1);
                        q2.add(node2.right);
                        a2.put(node2.right,node2);
                    }
                }
            }else if(node1.left==null && node2.left!=null){
                if(node1.right==null){
                    return false;
                }
                if(node2.right!=null){
                    return false;
                }
                if(node1.right.val!=node2.left.val){
                    return false;
                }else{
                    q1.add(node1.right);
                    a1.put(node1.right,node1);
                    q2.add(node2.left);
                    a2.put(node2.left,node2);
                }              
            }else if(node1.left!=null && node2.left==null){
                if(node1.right!=null){
                    return false;
                }
                if(node2.right==null){
                    return false;
                }
                if(node1.left.val!=node2.right.val){
                    return false;
                }else{
                    q1.add(node1.left);
                    a1.put(node1.left,node1);
                    q2.add(node2.right);
                    a2.put(node2.right,node2);
                }
            }else{
                if(node1.left.val!=node2.left.val){
                    if(node2.right==null){
                        return false;
                    }
                    if(node1.right==null){
                        return false;
                    }
                    if(node1.left.val!=node2.right.val){
                        return false;
                    }else{
                        q1.add(node1.left);
                        a1.put(node1.left,node1);
                        q2.add(node2.right);
                        a2.put(node2.right,node2);
                    }
                    if(node1.right.val!=node2.left.val){
                        return false;
                    }else{
                        q1.add(node1.right);
                        a1.put(node1.right,node1);
                        q2.add(node2.left);
                        a2.put(node2.left,node2);
                    }

                }else{
                    if(node1.right==null && node2.right!=null){
                        return false;
                    }else if(node1.right!=null && node2.right==null){
                         return false;
                    }else if(node1.right!=null && node2.right!=null){
                        if(node1.right.val!=node2.right.val){
                            return false;
                        }else{
                            // System.out.println(node1+" "+node2);
                            q1.add(node1.left);
                            a1.put(node1.left,node1);
                            q2.add(node2.left);
                            a2.put(node2.left,node2);
                            q1.add(node1.right);
                            a1.put(node1.right,node1);
                            q2.add(node2.right);
                            a2.put(node2.right,node2);
                        }
                    }
                }
            }


        }

        //System.out.println()

        if(q1.isEmpty() && q2.isEmpty()){
            return true;
        }

        return false;

    }
}

Итак, когда я отправляю это решение, я прохожу 71/72 контрольных примеров и провалюсь в одном случае. Я не могу выяснить, в чем проблема с моим кодом.

Неудачный тестовый пример выглядит следующим образом:

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

[0,1,2,3,8,9,4,33,14,18, ноль, 11,10,5,6,94,72,16,54,30,21,27 , 53,17,13,25, нуль, 7,12, NULL, NULL, NULL, 73,26,19, NULL, NULL, NULL, NULL, 24,37,28,59, нуль, 56,20, нуль , 97,36, нуль, 62,49,40,15, NULL, NULL, NULL, NULL, 74,34, нуль, 52,32,39, нуль, 29, нуль, 67,87, NULL, NULL, 22 , NULL, NULL, NULL, 66,41, NULL, NULL, NULL, 85,47,42,35,50, NULL, NULL, NULL, NULL, NULL, NULL, 38,55, нуль, 76,58, нуль , NULL, NULL, NULL, NULL, 31,23, NULL, NULL, NULL, 43,92, NULL, NULL, NULL, 84, нуль, 95, нуль, 96, NULL, 64,45, нуль, 57, нулевая , нуль, 61, нуль, 46,60, нуль, 69,93,44, NULL, NULL, NULL, NULL, 99, NULL, NULL, NULL, NULL, NULL, 48,51,68,83, NULL, NULL , 65,81, NULL, NULL, NULL, 88, NULL, NULL, NULL, NULL, NULL, NULL, 70,63, NULL, NULL, NULL, 71, NULL, NULL, 75, NULL, NULL, NULL, 91 , NULL, NULL, NULL, 79,77,78,98, нуль, 90, NULL, NULL, NULL, NULL, 80,82, нуль, 86, NULL, NULL, NULL, NULL, NULL, NULL, 89]

[0,2,1,4,9,8,3,6, 5,11,10,18, нулевая 33,14,7,12, нуль, 25,27,53,13,17,30,21,72,94,16,54,40,49,15, нуль, 62, нуль, 59,28, нуль, 56,36,97,20, NULL, NULL, NULL, 37,24,73, NULL, NULL, NULL, 26,19, NULL, NULL, 47,42, нуль, 85,35,50, NULL, NULL, 67,87,29, NULL, NULL, NULL, 41,66, NULL, NULL, 22, нуль, 39, нуль, 32,52, NULL, NULL, 74, нулевой нуль, 34, NULL, NULL, NULL, 84,92, нуль, 95, NULL, NULL, 96, NULL, NULL, NULL, NULL, 58, NULL, NULL, 43, NULL, NULL, 23,31, нулевой, 76,55,38, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, 99, NULL, NULL, 61, нуль, 44,93,69, нуль, 60,46, NULL, NULL, NULL, 57,64,45, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, 88, NULL, NULL, 65,81,83,68, NULL, NULL, 48, 51,91, нуль, 75, NULL, NULL, NULL, 98, NULL, NULL, 71,63,70, NULL, NULL, NULL, NULL, NULL, 90, NULL, NULL, NULL, 78,77,79, NULL, NULL, NULL, NULL, NULL, 86,80,82, NULL, NULL, NULL, NULL, NULL, NULL, NULL, 89]

Ожидаемый результат для этого случая false но я возвращаюсь true

Было бы здорово, если бы кто-то мог указать мне, где и почему я ошибаюсь в этом.

SomeDude · Answer 1 · 11 февраля 2020

Я не уверен, почему вы решили проблему, думая, что обход уровня порядка. Его трудно прочитать из кода. Но на самом деле проблему легко решить. Вам не нужен обход уровня заказа.

Существует два условия:

root Значения не равны:

Этот случай тривиален, сразу возвращает false, потому что нет смысла переворачивать левые, правые поддеревья. Значения

root равны:
- В этом случае вы можете сначала проверка без переворота: если левое поддерево и правое поддерево root равны соответствующему левому поддереву и правому поддереву второго root, то вам не нужно переворот, просто вы возвращаете true.
- Если они не равны, попробуйте перевернуть, т. Е. Вам нужно проверить
  
  first root left поддерево == second root right поддерево &
  
  first root правое поддерево == second root левое поддерево

Вам не нужно переворачивать элементы, просто проверьте равенство .

Код:

     public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if ( root1 == null && root2 != null ) return false;
        if ( root2 == null && root1 != null ) return false;
        if ( root1 == null && root2 == null ) return true;
        if ( root1.val != root2.val ) return false;
        boolean isLeftEqual = flipEquiv(root1.left, root2.left);
        boolean isRightEqual = flipEquiv(root1.right, root2.right);
        if ( !isLeftEqual || !isRightEqual ) {
            isLeftEqual = flipEquiv(root1.left, root2.right);
            isRightEqual = flipEquiv(root1.right, root2.left);
        }
        return isLeftEqual && isRightEqual;
    }

Sarel Foyerlicht · Answer 2 · 11 февраля 2020

попробуйте это: (вы не проверяли, когда оба ушли)

class Solution {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
        Map<TreeNode,TreeNode> a1 = new HashMap<>();
        Map<TreeNode,TreeNode> a2 = new HashMap<>();
        if(root1!=null){
            q1.add(root1);
            a1.put(root1,null);
        }
        if(root2!=null){
            q2.add(root2);
            a2.put(root2,null);
        }

        while(!q1.isEmpty() && !q2.isEmpty()){
            TreeNode node1 = q1.poll();
            TreeNode node2 = q2.poll();

            //System.out.println(node1.val +" "+node2.val+" ");

            if(node1.val!=node2.val){
                return false;
            }

            if(a1.get(node1)==null){
                if(a2.get(node2)!=null){
                    return false;
                }
            }else{
                if(a2.get(node2)==null){
                    return false;
                }
                // System.out.println(node1.val +" "+node2.val+" "+a1.get(node1).val+" "+a2.get(node2).val+" "+node1+" "+node2);
                if(a1.get(node1).val!=a2.get(node2).val){
                    return false;
                }
            }

            //System.out.println(node1+" "+node2);

            //1 right 2 right
            if(node1.left==null && node2.left==null){
                if(node1.right==null && node2.right!=null){
                    return false;
                }else if(node1.right!=null && node2.right==null){
                    return false;
                }else if(node1.right!=null && node2.right!=null){
                    if(node1.right.val!=node2.right.val){
                        return false;
                    }else{
                        q1.add(node1.right);
                        a1.put(node1.right,node1);
                        q2.add(node2.right);
                        a2.put(node2.right,node2);
                    }
                }
            }
            //add this
            //1 left 2 left
            else if(node1.right==null && node2.right==null){
                if(node1.left==null && node2.left!=null){
                    return false;
                }else if(node1.left!=null && node2.left==null){
                    return false;
                }else if(node1.left!=null && node2.left!=null){
                    if(node1.left.val!=node2.left.val){
                        return false;
                    }else{
                        q1.add(node1.left);
                        a1.put(node1.left,node1);
                        q2.add(node2.left);
                        a2.put(node2.left,node2);
                    }
                }
            }
            //1 right 2 left
            else if(node1.left==null && node2.left!=null){
                if(node1.right==null){
                    return false;
                }
                if(node2.right!=null){
                    return false;
                }
                if(node1.right.val!=node2.left.val){
                    return false;
                }else{
                    q1.add(node1.right);
                    a1.put(node1.right,node1);
                    q2.add(node2.left);
                    a2.put(node2.left,node2);
                }              
            }
            //1 left 2 right
            else if(node1.left!=null && node2.left==null){
                if(node1.right!=null){
                    return false;
                }
                if(node2.right==null){
                    return false;
                }
                if(node1.left.val!=node2.right.val){
                    return false;
                }else{
                    q1.add(node1.left);
                    a1.put(node1.left,node1);
                    q2.add(node2.right);
                    a2.put(node2.right,node2);
                }
            }else{
                // 1 left right 2 left right
                if(node1.left.val!=node2.left.val){

                    if(node2.right==null){
                        return false;
                    }
                    if(node1.right==null){
                        return false;
                    }

                    if(node1.left.val!=node2.right.val){
                        return false;
                    }else{
                        q1.add(node1.left);
                        a1.put(node1.left,node1);
                        q2.add(node2.right);
                        a2.put(node2.right,node2);
                    }

                    if(node1.right.val!=node2.left.val){
                        return false;
                    }else{
                        q1.add(node1.right);
                        a1.put(node1.right,node1);
                        q2.add(node2.left);
                        a2.put(node2.left,node2);
                    }

                }else{
                    if(node1.right==null && node2.right!=null){
                        return false;
                    }else if(node1.right!=null && node2.right==null){
                         return false;
                    }else if(node1.right!=null && node2.right!=null){
                        if(node1.right.val!=node2.right.val){
                            return false;
                        }else{

                            q1.add(node1.left);
                            a1.put(node1.left,node1);
                            q2.add(node2.left);
                            a2.put(node2.left,node2);

                            q1.add(node1.right);
                            a1.put(node1.right,node1);
                            q2.add(node2.right);
                            a2.put(node2.right,node2);
                        }
                    }
                }
            }


        }

        System.out.println(a1.size());

        if(q1.isEmpty() && q2.isEmpty()){
            return true;
        }

        return false;

    }
}

(вы пропускаете, когда оба только что покинули узел, поэтому вы не путешествуете по всему дереву)

Отразить эквивалентные двоичные деревья в LeetCode

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 2 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Отразить эквивалентные двоичные деревья в LeetCode

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 2 ]

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Похожие темы