найти максимальное поддерево

Question

Это спрашивается во время интервью, я пытаюсь понять, как решить эту проблему.

В двоичном дереве я пытаюсь найти максимальное поддерево, такое, что все узлы содержат 0 или 2 дочерних узла и все конечные узлы находятся на одном уровне узлов.

Пример:

    1
  /     \
2        3
 \      /   \
  4    5     6
      / \   / \ 
     7   8  9   10
               /    
              11

После удаления 1,2,4 и 11, мы получаем максимальное значение дерево размером 7 .

          3
        /   \
       5     6
      / \   / \ 
     7   8  9   10

Теперь с учетом узла дерева с левым и правым потомком:

class TreeNode {
    int data;
    TreeNode leftChild;
    TreeNode rightChild;
}           

Я нашел решение здесь , но он дает неправильный вывод для моего ввода.

Answer 1

//basic idea is that traveral the tree, while visiting current node, calculate the depth of the max prefect subtree with current node as the root. The depth of the final result subtree must be one of such depth(in fact, the maximum one).
class MaxPerfectSubtree{
    private int maxDepth=0;//global var for current depth of the max prefect subtree with current node as its root,updated while doing postorder traversal 
    public int solution(TreeNode root){
        postorder(root);//traversal the tree in a buttom-up style while updating the maxDepth
        return (int)Math.pow(2,maxDepth+1)-1;//with the max depth, the max node count is trival.
    }
    private int postorder(TreeNode root){//returns the depth of the max prefect subtree with root as its root.
        if(root==null)
            return 0;//

        int left=postorder(root.left);
        int right=postorder(root.right);
        int curDepth=1+Math.min(left,right);//max prefect subtree with root as its root
        if(maxDepth<curDepth)
            maxDepth=curCount;
        return curDepth;
    }
}    

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

---

Обновление просто найдено что помимо количества узлов также необходим обход по дереву, как показано в приведенной ссылке (который c означает, что дерево также требуется).

Таким образом, мы можем добавить глобальный TreeNode переменная для записи узла root, соответствующего глобальной переменной maxDepth.

А затем переупорядочить этот TreeNode в стиле верхней кнопки, с левой глубиной в качестве параметра функции обхода inorder, чтобы мы могли разбить, как только мы достигнем максимальной глубины.

Answer 2

У меня была такая же задача в тесте онлайн-кодирования всего 2 дня go. К сожалению, я выполнил задание с небольшой ошибкой и получил 0% за это задание.

Хотя я не уверен, что это правильно, но я думаю, что так и должно быть.

    public static int solution(Tree tree) {
        return solution(tree, 0)[0];
    }

    public static int[] solution(Tree tree, int level) {
        int[] result = new int[]{0, level};

        if (tree != null) {
            int[] resultLeft = solution(tree.l, level + 1);
            int[] resultRight = solution(tree.r, level + 1);

            if (resultLeft[0] == resultRight[0] && resultLeft[1] == resultRight[1]) {
                result[0] = 1 + resultLeft[0] + resultRight[0];
                result[1] = resultLeft[1];
            } else if (resultLeft[0] > resultRight[0]) {
                result = resultLeft;
            } else {
                result = resultRight;
            }
        }

        return result;
    }