Java. Help me understand the binary tree task

Question

Java. Help me understand the binary tree task

I don't quite understand how to build the tree itself.

In this problem, we consider binary trees. The figure below shows an example of a binary tree consisting of seven nodes.

A binary tree is either an empty tree or a node (called a root) that contains a single integer value and is connected to two other binary trees. We are interested in paths (sequences of connected adjacent nodes) that start at the root and follow beyond the edges of the tree (marked with arrows in the figure above). For example, the sequence of nodes A, B, D is a valid path, but the sequence a, B, G is not.

We want to find the maximum number of different values that appear on the path, starting from the root of the tree. For example, on a path consisting of nodes A, B, D, G, there are two different values (4 and 5). There are three different values on the path A, C, E (1, 4, and 6). There is no path, containing four or more different values.

Write a function: solution of the class { public int solution (Tree T);}

This, given a binary tree T consisting of N nodes, returns the maximum number of distinct values that appear on the path starting at the root of the tree T. for example, given the tree shown above, the function should return 3.

Technical details

A binary tree is defined using a data structure the pointer. Suppose the following declarations are given:

public class Tree {
    public int x;
    public Tree l;
    public Tree r;
}

An empty tree is represented by an empty pointer (denoted by null). A non-empty tree is represented by a pointer to an object that represents its root. The x attribute contains an integer contained in the root, while the l and r attributes contain the left and right subtrees of the binary tree, respectively.

Biases

Write an efficient algorithm for the following assumptions: * N is an integer in range [1..50,000]; * the height of the tree t (the number of edges on the longest path from the root to the leaf) is in the range [0..3,500]; • each value in the T tree is an integer in the range [1..Northern.]

@NamEfamily Thought like this

public void  preOrder(Tree tree){
        if (tree == null){
            return;
        }

//тут делать что нибудь со значением листка
        preOrder(tree.l);
        preOrder(tree.r);
    }
}

0

алгоритм java binary tree

Author: A K, 2019-07-10

Source

1 answers

score 1 · Accepted Answer

For convenience, you can make two constructors: to create a node with a number and a node with its associated nodes.

public class Tree {
    public int x;
    public Tree l;
    public Tree r;

    public Tree(int x) {
        this.x = x;
    }

    public Tree(int x, Tree l, Tree r) {
        this.x = x;
        this.l = l;
        this.r = r;
    }
}

Creating a tree will look like this:

Tree tree = new Tree(4,
                new Tree(2, 
                        new Tree(5), null),
                new Tree(2,
                        new Tree(3,
                                new Tree(5),
                                new Tree(4)),
                        new Tree(2)));

In this way, you can traverse the entire tree and get the maximum number of different node numbers in the tree:

HashSet<Integer> gatheredValues = new HashSet<>();

public int solution(Tree tree) {
    if(tree == null) return gatheredValues.size();

    boolean notContains = !gatheredValues.contains(tree.x);
    if(notContains) gatheredValues.add(tree.x);

    if(gatheredValues.size() == 3) return 3;

    // int maxValue = Math.max(solution(tree.l),solution(tree.r)). заменено для экономии времени (узлов всё-таки может быть до 50 тысяч!)
    int lValue = solution(tree.l);
    int rValue = solution(tree.r);
    int maxValue = (lValue >= rValue) ? lValue : rValue;

    if(notContains) gatheredValues.remove(tree.x);

    return maxValue;
}