maximum length of a descending path in a tree whic

问题:

I'm prepearing for tech interview, so basically learning algorithms from very beginning :) we are given a BST. I need to find the max length of a desc path in it, which always goes left or right In other words, an example tree's descending path is 2, ie 15-10-6

   5
  / \
2     15
     /
    10
   / \ 
  6   14

I'm very new to algorithmic problems.what are my steps to solving this?

My idea was to use DFS and a counter to store the longest path. but I can't figure out how to employ recursion to do the job, whereas recursion seems more natural for this data structure.

any suggestions/directions?

回答1:

The wording is a little confusing, but I think you mean the maximum of

• the maximum length of a path that starts at any node and then only goes to the left, or
• the maximum length of a path that starts at any node and then only goes to the right.

You do this in two passes, one to find the max left path and one to find the max right path (and then take the max of those two). Or you can do it in a single pass that does both at once.

For every node, you want to know three values:

1. the length of the left path starting at that node,
2. the length of the right path starting at that node, and
3. the length of the longest path starting at that node or one of its descendants.

If you are doing this recursively, this means the recursion should return these three values, probably as a small array or as a simple three-field object.

This would look something like

Results calculate(Tree node) {
    if (node == null) return new Results(0,0,0);
    else {
        Results leftResults = calculate(node.left);
        Results rightResults = calculate(node.right);
        int leftLength = 1 + leftResults.leftLength;
        int rightLength = 1 + rightResults.rightLength;
        int maxLength = Math.max(Math.max(leftLength, rightLength), 
                                 Math.max(leftResults.maxLength, rightResults.maxLength));
        return new Results(leftLength, rightLength, maxLength);
    }
}

and the overall result would just be calculate(root).maxLength.

回答2:

Non-recursive solution

Actually, this is a problem on Codibility which I was tested for. I am just mentioning a non-recursive solution for the sake of discussing it.

The tree has itself a value which can be modified.

I found a better solution than the recursive solution here but I do not program in Java, so I will put the C# solution which is correct algorithmic wise:

public class Tree
{
    public int x;
    public Tree l;
    public Tree r;
}
class solution
{
    public int solution(Tree T)
    {
        // write your code in C# 5.0 with .NET 4.5 (Mono)
        List<Tree> toProcess = new List<Tree>(10000);

        if (T == null)
            return 0;
        int maxLength = 0;
        T.x = 0;
        toProcess.Add(T);

        while (toProcess.Count != 0)
        {
            Tree currNode = toProcess[toProcess.Count-1];
            toProcess.RemoveAt(toProcess.Count - 1);
            int reminder = currNode.x % 100000;
            if (currNode.l != null)
            {
                currNode.l.x = 1 + reminder;
                maxLength = Math.Max(maxLength, currNode.l.x);
                toProcess.Add(currNode.l);
            }
            if (currNode.r != null)
            {
                currNode.r.x = 100000 + (currNode.x - reminder);
                maxLength = Math.Max(maxLength, currNode.r.x / 100000);
                toProcess.Add(currNode.r);
            }
        }
        return maxLength;
    }
}

This is faster than recusion by multiples if you time it. The idea is at each node, you store a longer length in the children nodes and append them to a list (you could have used a stack if you wanted) to process later. You use the int to store the count. The original problem on Codibility mentioned that there are no more than 10 000 nodes and the max depth is 800.

A last optimisation is to replace my use of 100000 to separate left and right length by a binary shift which would be faster, i.e. use the 16 first bits to store length on the left and the remaining for length on the right, but I did not have enough time to do this as I started with the recursive method.

EDIT: I did the bitwise one, too bad I did not have time to make sure it was correct and submit it because it is much faster than the recursive one:

    public int solution(Tree T)
    {
        // write your code in C# 5.0 with .NET 4.5 (Mono)
        List<Tree> toProcess = new List<Tree>(10000);

        int rightmask = 0x0000FFFF;
        int leftmask = ~0x0000FFFF;
        if (T == null)
            return 0;
        int maxLength = 0;
        T.x = 0;
        toProcess.Add(T);

        while (toProcess.Count != 0)
        {
            Tree currNode = toProcess[toProcess.Count-1];
            toProcess.RemoveAt(toProcess.Count - 1);

            if (currNode.l != null)
            {
                int leftpart = (currNode.x & leftmask) >> 16;
                int newLength = 1 + leftpart;
                currNode.l.x = newLength << 16;
                maxLength = Math.Max(maxLength, newLength);
                toProcess.Add(currNode.l);
            }
            if (currNode.r != null)
            {
                int rightpart = (currNode.x & rightmask);
                currNode.r.x = 1 + rightpart;
                maxLength = Math.Max(maxLength, currNode.r.x);
                toProcess.Add(currNode.r);
            }
        }
        return maxLength;
    }

回答3:

Idea:

The recursive function called from node v should return 3 values:

1. Maximum descending path which goes always left or always right in subtree rooted in v

2. Maximum length of path which goes always left starting from v

3. Maximum length of path which goes always right starting from v

Let's call these values respectively (V1, V2, V3)

Base case:

Clearly, for any leaf in the tree, all above values are equal 0.

Recursive call:

Let's consider any internal node v.

Let (L1, L2, L3) be the values returned by a recursive call to left child of v.

Let (R1, R2, R3) be the values returned by a recursive call to right child of v.

Then v, in order to compute (V1, V2, V3) only has to combine results returned from the left and the right child:

V2 is equal to L2 + 1 if the left child exists. Otherwise, it's 0.

V3 is equal to R3 + 1 if the right child exists. Otherwise, it's 0.

V1 is equal to max(L1, R1, V2, V3)

回答4:

Here is the working code for the question. An 11-node binary tree is given for testing:

public class Node {

int L = 0;
int R = 0;

Node left = null;
Node right = null;

}

public class BTree {

void calculate_paths(Node root) {

    if (root.left != null) {
        calculate_paths(root.left);
        root.L = root.left.L + 1;
    }

    if (root.right != null) {
        calculate_paths(root.right);
        root.R = root.right.R + 1;
    }
}

int max_paths(Node root) {

    int maxL = 0;
    int maxR = 0;

    if (root.left != null) maxL = max_paths(root.left);
    if (root.right != null) maxR = max_paths(root.right);

    return Math.max(Math.max(root.L, root.R), Math.max(maxL, maxR));

}

}

public class Main {

public static void main(String[] args){
    System.out.println("Let the challenge begin!");

    //create the tree
    Node n0 = new Node();
    Node n1 = new Node();
    Node n2 = new Node();
    Node n3 = new Node();
    Node n4 = new Node();
    Node n5 = new Node();
    Node n6 = new Node();
    Node n7 = new Node();
    Node n8 = new Node();
    Node n9 = new Node();
    Node n10 = new Node();

    n0.right = n1;
    n0.left = n7;

    n1.left = n2;

    n2.left = n3;
    n2.right = n4;

    n4.right = n5;

    n5.right = n6;

    n6.left = n9;
    n6.right = n10;

    n7.left = n8;


    BTree Tree = new BTree();

    Tree.calculate_paths(n0);
    System.out.println(Tree.max_paths(n0));

}

}

回答5:

Java implementation:

    // auxiliary method, starts the recursion:    

    public int height(){
        if(root != null) // If not null calculate height
            return height(root);
        else // height is zero...
            return 0;
    }

    // Gets the job done:
    private int height(BinaryTreeNode<T> node){

        int right = 0, left = 0;

        if (node.getLeftChild() != null) // count and calculate left path height
            left= 1+ height(node.getLeftChild()); 
        if (node.getRightChild() != null) // count and calculate right path height
            right= 1 + height(node.getRightChild());

        return Math.max(left, right);
    }