java - 二叉树广度优先搜索算法

Question

在二叉树 BFS 算法中，有人可以帮助我理解为什么我们在下面的代码中执行 height - 1 吗？我写了这段代码，但它从来没有工作过，直到我在网上发现你需要做一个高度 - 1。

public class BreadthFirstSearch {

public static int calculateHeightOfTree(Node root) {
    if (root == null) {
        return 0;
    } else {
        return 1 + Math.max(calculateHeightOfTree(root.leftNode), calculateHeightOfTree(root.rightNode));
    }
}

public static void printDataAtAllLevels(Node root, int height) {
    for (int i = 1; i <= height; i++) {
        printDataAtGivenLevel(root, i);
    }
}

public static void printDataAtGivenLevel(Node root, int height) {
    if (root == null) {
        return;
    }
    if (height == 1) {
        System.out.println(root.data);
    } else {
        printDataAtGivenLevel(root.leftNode, height - 1);
        printDataAtGivenLevel(root.rightNode, height - 1);
    }
}

public static void main(String[] args) {
    Node node = new Node(1);
    node.leftNode = new Node(2);
    node.rightNode = new Node(3);
    node.leftNode.leftNode = new Node(4);
    node.leftNode.rightNode = new Node(5);

    System.out.println("Level order traversal of binary tree is ");
    int height = calculateHeightOfTree(node);
    System.out.println("HEIGHT: " + height);
    printDataAtAllLevels(node, height);
}

Answer 1

那么，如果要打印树的第n层数据，相当于打印左右子树的第n-1层数据。因此，当您将左右子树传递给递归调用时，您应该请求打印级别减少1的数据。

例如，由于树的根的级别为 1，因此根的左右子节点的级别为 2。所以如果你想打印原树的所有level 2的数据，相当于打印左右子树的level 1的数据。