java - 打印所有高于所有叶节点的 N 级节点

Question

我需要打印在所有叶节点之上的所有 N 级节点。我尝试了以下方法，但现在我卡住了，无法继续。请帮忙。我需要仅使用 Java 7 编写代码，而无需使用其他版本。

例如，我有这条路径 1 --> 2 --> 3 --> 4，所以在这种情况下假设 4 是我的叶节点，node 3 比 4 高 1 级，节点 2 比叶节点 4 和节点 1 高 2 级 比叶节点 4 高 3 级。

注意:请仅使用 Java 7。

public class NNodeBeforeLeaf {

    static Node root;
    static class Node {
        int data;
        Node left, right;
        Node(int data){
            this.data = data;
            left=right=null;
        }
    }

    public static boolean isLeaf(Node n){
        if(n.right == null && n.left == null)
            return true;
        return false;
    }

    public static void main(String[] args) {
        int level = 2;      // level N
        root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(8);

        print(root, 0, level);
    }

    public static void print(Node n, int currLevel, int level){
        if(n == null){
            return;
        }
        if(!isLeaf(n)){
            print(n.left, currLevel + 1, level);
            print(n.right, currLevel + 1, level);
        }
        printNode(n, currLevel, level);
    }

    public static void printNode(Node n, int currLevel, int level){}

}

Answer 1

你的结构中有一个错误，一个节点知道它的子节点但不知道它是父节点，所以你需要构建一个结构来给你这个链接:这是我的建议:我构建一个给我父节点的映射使用方法 buildParentMap 关联到一个节点这个函数已经在一次传递中列出了所有的叶子以避免在你的树上进行两次迭代然后我使用这个 map 在我列出的每个叶子上上升尽可能多的时间我列出之前这里是一个片段

请注意这段代码的工作，但如果您试图提升该根或者如果同一节点出现在太多子节点中(但具有相同数据的 2 个节点不会有问题)，则没有安全性

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;

public class NNodeBeforeLeaf {

    static Node root;

    static class Node {
        int data;
        Node left, right;

        Node(int data) {
            this.data = data;
            left = right = null;
        }

        @Override
        public String toString() {
            return "Node : " + data;
        }
    }

    public static boolean isLeaf(Node n) {
        if (n.right == null && n.left == null)
            return true;
        return false;
    }

    public static void main(String[] args) {
        int level = 2; // level N
        root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(8);

        print(root, 0, level);

        int levelToUp = 1;
        HashSet<Node> result = getUpper(levelToUp, root);

        System.out.println(Arrays.toString(result.toArray()));
    }

    private static HashSet<Node> getUpper(int levelToUp, Node node) {
        HashMap<Node, Node> parenttMap = new HashMap<Node, Node>();
        LinkedList<Node> leafs = new LinkedList<Node>();
        buildParentMap(node, parenttMap, leafs);
        HashSet<Node> result = new HashSet<>();
        for (Node leaf : leafs) {
            result.add(getUpperLevel(leaf, levelToUp, parenttMap));
        }
        return result;
    }

    private static Node getUpperLevel(Node leaf, int i, HashMap<Node, Node> parenttMap) {
        Node tmp = leaf;
        while (i > 0) {
            i--;
            tmp = parenttMap.get(tmp);
        }
        return tmp;
    }

    private static void buildParentMap(Node root2, HashMap<Node, Node> hashMap, LinkedList<Node> leaf) {
        if (root2 == null) {
            return;
        } else if (isLeaf(root2)) {
            leaf.add(root2);
        } else {
            hashMap.put(root2.left, root2);
            buildParentMap(root2.left, hashMap, leaf);
            hashMap.put(root2.right, root2);
            buildParentMap(root2.right, hashMap, leaf);
        }
    }

    public static void print(Node n, int currLevel, int level) {
        if (n == null) {
            return;
        }
        printNode(n, currLevel, level);
        if (!isLeaf(n)) {
            print(n.left, currLevel + 1, level);
            print(n.right, currLevel + 1, level);
        }
    }

    public static void printNode(Node n, int currLevel, int level) {
        String output = "";
        for (int i = 0; i < currLevel; i++) {
            output += "\t";
        }
        System.out.println(output + n);
    }

}