Demo Sistemul de abateri

 Aplicația DRPCIV la care am lucrat 2023 - 2024 - "Faults management" (Abateri).

50 DSA-Questions: #30, #31, #32

import java.util.LinkedList;
import java.util.Queue;

public class TreeElem {
    private Integer data;
    private TreeElem leftChild;
    private TreeElem rightChild;

    public TreeElem(Integer data) {
        this.data = data;
    }

    public Integer getData() {
        return data;
    }

    public void setData(Integer data) {
        this.data = data;
    }

    public TreeElem getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(TreeElem leftChild) {
        this.leftChild = leftChild;
    }

    public TreeElem getRightChild() {
        return rightChild;
    }

    public void setRightChild(TreeElem rightChild) {
        this.rightChild = rightChild;
    }

    private static TreeElem buildFrom(TreeElem treeElem, int k, Integer[] elements) {
        if (treeElem.getData() == null) {
            return treeElem;
        }
        if (elements.length > 2 * k + 1) {
            TreeElem left = new TreeElem(elements[2 * k + 1]);
            TreeElem right = new TreeElem(elements[2 * k + 2]);
            treeElem.setLeftChild(buildFrom(left, 2 * k + 1, elements));
            treeElem.setRightChild(buildFrom(right, 2 * k + 2, elements));
        }
        return treeElem;
    }

    public static TreeElem buildFrom(Integer[] elements) {
        if (elements.length == 0) {
            return null;
        }
        TreeElem root = new TreeElem(elements[0]);
        return buildFrom(root, 0, elements);
    }

    public static void printTreeBF(TreeElem root) {
        if (root != null) {
            Queue<TreeElem> queue = new LinkedList<>();
            queue.add(root);

            while (!queue.isEmpty()) {
                TreeElem treeElem = queue.poll();
                System.out.print(treeElem.getData() + ", ");
                if (treeElem.getLeftChild() != null) {
                    queue.add(treeElem.getLeftChild());
                }
                if (treeElem.getRightChild() != null) {
                    queue.add(treeElem.getRightChild());
                }
            }
        }
        System.out.println();
    }

    public static void printTreeDF(TreeElem root) {
        if (root != null) {
            System.out.print(root.getData() + ", ");
            if (root.getLeftChild() != null) {
                printTreeDF(root.getLeftChild());
            }
            if (root.getRightChild() != null) {
                printTreeDF(root.getRightChild());
            }
        }
    }

}

#30. Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

public class Exercise30 {
    private static final Integer[] ELEMENTS = {3,9,20,null,null,15,7}; // 3
    // private static final Integer[] ELEMENTS = {1,7,9,2,6,null,9,null, null, 5, 11, null, null, 5, null}; // 4
    // private static final Integer[] ELEMENTS = {1}; // 1
    // private static final Integer[] ELEMENTS = {}; // 0

    private int findMaxHeight(TreeElem elem, int k) {
        if (elem == null) {
            return k-1;
        }
        if (elem.getData() == null) {
            return k;
        }

        int leftMaxLevel = findMaxHeight(elem.getLeftChild(), k+1);
        int rightMaxLevel = findMaxHeight(elem.getRightChild(), k+1);

        return Math.max(leftMaxLevel, rightMaxLevel);
    }

    public static void main(String args[]) {
        TreeElem root = TreeElem.buildFrom(ELEMENTS);
        System.out.println("Max tree level = " + new Exercise30().findMaxHeight(root, 1));
    }
}

#31. Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

public class Exercise31 {
    private static final Integer[] LIST_1 = {3,9,20,null,null,15,7};
    // private static final Integer[] LIST_1 = {};
    private static final Integer[] LIST_2 = {3,9,20,null,null,15,7};
    // private static final Integer[] LIST_2 = {3,9,20,null,null,15,8};
    // private static final Integer[] LIST_2 = {3};
    // private static final Integer[] LIST_2 = {};

    private boolean areIdentical(TreeElem root1, TreeElem root2) {
        if (root1 == null || root2 == null) {
            return root1 == root2;
        }
        if (root1.getData() != null && root2.getData() != null && root1.getData().equals(root2.getData())) {
            return areIdentical(root1.getLeftChild(), root2.getLeftChild()) && 
                    areIdentical(root1.getRightChild(), root2.getRightChild());
        }
        return root1.getData() == null && root2.getData() == null;
    }

    public static void main(String[] args) {
        TreeElem root1 = TreeElem.buildFrom(LIST_1);
        TreeElem root2 = TreeElem.buildFrom(LIST_2);
        System.out.println("Identical trees = " + new Exercise31().areIdentical(root1, root2));
    }
}

#32. Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root.

public class Exercise32 {
    // private static final Integer[] ROOT = {4,2,7,1,3,6,9}; // 4, 7, 2, 9, 6, 3, 1,
    private static final Integer[] ROOT = {4,8,9}; // 4,9,8

    private TreeElem solve(TreeElem root) {
        if (root == null) {
            return null;
        }

        TreeElem leftAux = root.getLeftChild();
        root.setLeftChild(root.getRightChild());
        root.setRightChild(leftAux);

        solve(root.getLeftChild());
        solve(root.getRightChild());

        return root;
    }

    public static void main(String[] args) {
        TreeElem root = TreeElem.buildFrom(ROOT);
        TreeElem inverted = new Exercise32().solve(root);
        TreeElem.printTreeBF(inverted);
    }
}