Двоичное дерево - среди самых дальних от корня, самых дальних вправо

Question

У меня есть двоичное дерево.Среди всех самых дальних узлов от корня (высота дерева, на мой взгляд) мне нужно найти самые дальние справа от этих узлов.

Пример 1:

      M
     / \
    G   N
   / \   \
  D   H   O
 / \       \
B   F       Q

Самый дальнийсправа среди самых дальних узлов от корня находится 'Q'.

Пример 2:

      M
     / \
    G   N
   / \   \
  D   H   O
 / \       
B   F       

Самым дальним направлением среди самых дальних узлов от корня является 'F'.

Код, который я имею, может получить самый глубокий узел и вернуть самый правый узел (слева, если у самого глубокого узла нет правых потомков).Но затем я столкнулся с проблемой, где могут быть листья одинакового размера, и я не знал, как отследить и сравнить их все, чтобы найти самый дальний (что в данном случае будет 'Q')

Я узнал, как найти максимальную высоту дерева, но не то, как внедрить это в мой код

Это то, что я пока имею:

public void find(Node<T> r) {   

    if(r.right == null) { // Are there any children to the right?
        if(r.left.size() > 1) {
            find(r.left); // If not, we go left if there are more than 1
        }

        if(r.left.size() == 1) { //
            rNode = r.left.data;
        }

    }

    if(r.left == null) { // Are there any children to the left?
        if(r.right.size() > 1) {
            find(r.right); // If not, we go right if there are more than 1
        }

        if(r.right.size() == 1) {
            rNode = r.right.data; // If the right is the only node left, pick it as the answer
        }
    }

    if(r.left != null && r.right != null) { // Are there children to the left and right?
        if(r.left.size() == r.right.size()) { // 
            if(r.left.size() == 1) { // If we have 1 child to the right and left, pick the right child
                rNode = r.left.data; // If the left is the only node left, pick it as the answer
            } 
        }

        if(r.left.size() > r.right.size()) { // Are there more to the left?
            find(r.left); // Proceed
        }

        if(r.left.size() < r.right.size()) { // Are there more to the right?
            find(r.right); // Proceed
        }
    } 

}

public int maxDepth(Node<T> r) {

     if(r == null){
         return 0;
     }

     int leftDepth = maxDepth(r.left);
     int rightDepth = maxDepth(r.right);

     return Math.max(leftDepth, rightDepth)+1;     
 }


/**
 * Among all the nodes which are farthest from the root, find the one which is
 * farthest to the right.
 * 
 * @return data value of said node
 */
public T findRightmostLowest() {
    if(root.size() == 1) return root.data;

    find(root);
    return rNode;
}

Answer 1

Проблемы с деревом почти всегда имеют такие же рекурсивные, как и нерекурсивные решения.И обычно рекурсивный намного проще.Если проблема в порядке, то это может выглядеть так:

public static <T> Node<T> getRootFurthest(Node<T> root) {
    return findFurthest(root, 0, new NodeDepth<>()).node;
}

private static <T> NodeDepth<T> findFurthest(Node<T> node, int depth, NodeDepth<T> furthest) {
    if (node == null)
        return furthest;

    // >= - rigth node of equal depth
    // >  - left node of equal depth
    if (depth >= furthest.depth) {
        furthest.node = node;
        furthest.depth = depth;
    }

    findFurthest(node.left, depth + 1, furthest);
    findFurthest(node.right, depth + 1, furthest);

    return furthest;
}

И два поддерживаемых объявления класса:

private static final class NodeDepth<T> {

    private Node<T> node;
    private int depth = -1;
}

public static class Node<T> {

    private T val;
    private Node<T> left;
    private Node<T> right;
}

Answer 2

Я ценю помощь, она привела меня к правильному решению:

T rNode = null;
boolean found = false;

/**
 * Helper method that recursively finds Rightmost node between 
 * the nodes farthest from the root
 * 
 * @param r
 * @param depth
 * @param i - Our current level of the tree
 */
public void find(Node<T> r, int depth, int i) { 
    if(i == depth && found == false) { // Are we at the answer?
        rNode = r.data; // Dump node into our temporary node

        found = true;   // Change  found to true so we don't enter 
                        // the check a second time.
    }

    if(r.right != null) { // Are there children to the right?
        // If there is, does it lead to one of the farthest leaves?
        if((maxDepth(r.right) + i) == depth) {
            find(r.right, depth, i + 1); 
        }
    }

    if(r.left != null) { // Are there children to the left?
        // If there is, does it lead to one of the farthest leaves?
        if((maxDepth(r.left) + i) == depth) { 
            find(r.left, depth, i + 1);
        }
    }

}

/**
 * Find the height to our tree.
 * 
 * @param r
 * @return
 */
public int maxDepth(Node<T> r) {

     if(r == null){
         return 0;
     }

     int leftDepth = maxDepth(r.left);
     int rightDepth = maxDepth(r.right);

     return Math.max(leftDepth, rightDepth)+1;     
 }


/**
 * Among all the nodes which are farthest from the root, find the one which is
 * farthest to the right.
 * 
 * @return data value of said node
 */
public T findRightmostLowest() {

    rNode = null; // Reset the temporary node
    found = false; // Reset our boolean variable for helper method

    if(root.size() == 1) return root.data; // If tree has only 1 data point, return it

    find(root, maxDepth(root), 1); // Jump into the helper method

    return rNode; 
}