如何用递归在二叉搜索树中查找最大权重路径（Java实现）

我有一棵带权重边的二叉搜索树，需要编写递归遍历方法来查找最大权重路径。尝试用中序遍历实现，但代码存在问题，急需可行的实现示例。

我尝试的中序遍历代码 #

private static void inOrder(BinaryNode tree) {
if(tree == null) return;

if (tree is an end node) {
 update the end node array
}

if(tree.rightchild != null) {
       parent[rightChild.getLabel()] = tree;
}
if(tree.leftChild != null) {
       parent[leftChild.getLabel()] = tree;
}

inOrder(tree.leftChild);
inOrder(tree.rightChild);
}

支撑实现的相关类 #

BinaryNode类（允许修改） #

// Basic BinaryNode class, Feel free to edit this case.

public class BinaryNode {
    private String label; // 节点标签
    private BinaryNode[] childs; // childs[0]指向左子节点，childs[1]指向右子节点
    private int[] weights; // weights[0]是当前节点到左子节点的路径权重，weights[1]是到右子节点的路径权重
    private boolean edge;

    // 可添加额外字段和方法适配实现，但请勿修改已有内容，这些是构建树的必要部分

    // 构造方法
    public BinaryNode(String label, BinaryNode left, BinaryNode right, int lw, int rw) {
        this.label = label;
        this.childs = new BinaryNode[]{left, right};
        this.weights = new int[]{lw, rw};
    }

    // 访问器和修改器
    public BinaryNode getLeftChild() {
        return childs[0];
    }

    public void setLeftChild(BinaryNode child) {
        this.childs[0] = child;
    }

    public BinaryNode getRightChild() {
        return childs[1];
    }

    public void setRightChild(BinaryNode child) {
        this.childs[1] = child;
    }

    public int getLeftWeight() {
        return weights[0];
    }

    public void setLeftWeight(int weight) {
        this.weights[0] = weight;
    }

    public int getRightWeight() {
        return weights[1];
    }

    public void setRightWeight(int weight) {
        this.weights[1] = weight;
    }

    public String getLabel() {
        return this.label;
    }

    public String toString() {
        return "Node: " + this.label;
    }
}

BinaryTree类（禁止修改） #

// Don't Edit this class
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

public class BinaryTree {
    private BinaryNode root;
    private HashMap<String, BinaryNode> nodes;
    private ArrayList<String[]> fileLinesToProcess;
    
    public BinaryTree(){
        this.nodes = new HashMap<>(); 
        Scanner kb = new Scanner(System.in);
        this.fileLinesToProcess = customRead(kb);
        if(this.fileLinesToProcess.size() != 0){
            int i = 0;
            String[] shouldBeRoot = this.fileLinesToProcess.get(0);
            this.root = new BinaryNode(shouldBeRoot[0], null, null, 0, 0);
            this.nodes.put(shouldBeRoot[0], this.root);
            while(this.fileLinesToProcess.size() != i){
                String[] line = this.fileLinesToProcess.get(i);
                BinaryNode tnode = this.nodes.getOrDefault(line[0], null);
                BinaryNode othernode = this.nodes.getOrDefault(line[1], null);

                if(tnode == null){
                    tnode = new BinaryNode(line[0], null, null, 0, 0);
                }

                if(othernode == null){
                    othernode = new BinaryNode(line[1], null, null, 0, 0);
                }

                this.nodes.put(line[0], tnode);
                this.nodes.put(line[1], othernode);

                if(tnode.getLeftChild() == null){
                    tnode.setLeftChild(othernode);
                    tnode.setLeftWeight(Integer.parseInt(line[2]));
                }else{
                    tnode.setRightChild(othernode);
                    tnode.setRightWeight(Integer.parseInt(line[2]));
                }

                i++;
            }
        }
    }

    private ArrayList<String[]> customRead(Scanner fileInp){
        ArrayList<String[]> output = new ArrayList<>();
        while(fileInp.hasNext()){
            String[] nums = fileInp.nextLine().split(" ");
            output.add(nums);
        }
        return output;
    }

    public BinaryNode getRoot(){
        return this.root;
    }

    public static void turnBSTtoString(BinaryNode root){
        if(root == null) return;

        if(root.getLeftChild() != null){
            System.out.println(root.getLabel() + " " + root.getLeftChild().getLabel() + " " + root.getLeftWeight());
        }
        if(root.getRightChild() != null){
            System.out.println(root.getLabel() + " " + root.getRightChild().getLabel() + " " + root.getRightWeight());
        }

        turnBSTtoString(root.getLeftChild());
        turnBSTtoString(root.getRightChild());

        return;
    }
}

示例说明 #

• 示例输入：对应图示树的结构数据，每行包含父节点标签、子节点标签和路径权重
• 示例输出：该树的最大权重路径及总权重值

内容的提问来源于stack exchange，提问作者Bill