2

我想知道除此之外是否还有其他最佳解决方案。

问题：给定二叉树中的一个节点，我需要编写一个程序来找出与给定节点（包括）同级的所有节点。示例：如果给定节点是级别 2，则程序应返回高度为 2 的所有节点的集合。

我的解决方案：我有两种方法，一种是找出给定节点的根并返回根（此方法还找出从节点到根的高度（我的代码中的高度））并将这个根馈送到第二种方法进行广度优先搜索并在我遍历时不断更新节点的高度，如果队列中第一个元素的高度等于我在根方法中计算的高度，则返回队列。

我的代码：

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

public class binaryTree {
    int value;
    binaryTree left;
    binaryTree right;
    binaryTree parent;
    int height;
    static int bheight;

Queue<binaryTree> que = new LinkedList<binaryTree>();

public binaryTree(int v) {

    value = v;
}
//This method returns a Queue of all the nodes that are on the same level as the supplied node b.

public Queue<binaryTree> BFS(binaryTree b) {
    b = root(b);

    que.clear();
    b.height=0;
    que.add(b);
    while (!que.isEmpty()) {
        binaryTree node = que.remove();
        if (node.left != null) {

            node.left.height=(node.left.parent.height)+1;
            System.out.println(node.left.value+" Root is "+node.left.parent.value+" and its height is " + node.left.height);
            que.add(node.left);
        }
        if (node.right != null) {
            node.right.height=(node.right.parent.height)+1;
            System.out.println(node.right.value+" Root is "+node.right.parent.value+" and its height is " + node.left.height);
            que.add(node.right);
        }
        if(que.peek().height==bheight)
        {
        break;
        }

    }

    return que;
}


//Finds out the root of the given node and returns the root node
public binaryTree root(binaryTree t) {
    if (t.parent == null) {
        return t;
    } else {
        bheight++;

        return root(t.parent);

    }

} }
4

0 回答 0