java - 返回一个节点，其自身及其子节点在整个树中的总和最大，但即使当前总和较小，也会更新最大总和

Question

需要找到具有最大子节点和自身的节点。输入格式：

第 1 行：以空格分隔的级别顺序形式的元素（按照课堂上的做法）。订单是 -

每个元素的 Root_data、n (No_Of_Child_Of_Root)、n 个孩子等等

输出格式：总和最大的节点。

它返回正确的答案，但如果您通过取消注释打印语句运行代码，您可以看到最大和已更改，即使当前总和小于最大总和。

public class Solution {

/*  TreeNode structure 
 * 
 * class TreeNode<T> {
    T data;
    ArrayList<TreeNode<T>> children;

    TreeNode(T data){
        this.data = data;
        children = new ArrayList<TreeNode<T>>();
    }
}*/




public static TreeNode<Integer> maxSumNode(TreeNode<Integer> root){
        // Write your code here
        return maxSumNode(root, 0);
    }
    
    public static TreeNode<Integer> maxSumNode(TreeNode<Integer> root, int maxSum){
    
    if(root.children.size() == 0){
        return null;
        
    }
    
    TreeNode<Integer> maxNode = null;
    int tempSum = root.data;
    for(int i = 0 ; i < root.children.size() ; ++i){
        tempSum += root.children.get(i).data;
    }
    if(tempSum > maxSum){
        maxSum = tempSum;
        maxNode = root;
        
    }
    //System.out.println("MaxNum now for "+root.data+" is: "+ maxSum);
    
    for(int i = 0 ; i < root.children.size() ; ++i){
        TreeNode<Integer> temp = maxSumNode(root.children.get(i), maxSum);
        if(temp == null){
            continue;
        }
        if(temp != null){
            maxNode = temp;
        }
    }
    return maxNode;
}
}

例如，如果我给出输入： 5 3 1 2 3 1 15 2 4 5 1 6 0 0 0 0

我得到正确的输出，但 maxSum 很奇怪：

标签： javaalgorithmrecursiondata-structurestree

Answer 1

你的问题：

1. 设置 maxNode 时，不要检查它的旧值，
2. 并且您只能向下传递 maxNode，而不是向上/平行传递。将 int 作为参数传递是按值传递，因此您不是指的是全局值，而是每个方法调用都有自己的值。解决方案 1 直接解决了这个问题。

可能的解决方案：

1. 作为参数，您可以传递一些包含数字的类。引用本身会发生变化（按值传递），但寻址对象始终保持不变。所以你总是读/写同一个数字。

2. 或者您可以有一个成员变量（静态或非静态），但要非常小心访问。

3. 第三，您可以使用添加所有结果的统计图或优先级队列，当所有结果都完成后，您选择最大值。

参数解法是最简单、最安全、最有效的。如果 maxSumNode 同时运行多次，则静态更容易，但非常不安全。最后一个很简单，但效率不高。

/更新：

这是解决方案 #1 的示例。和一个测试。这有很多额外的代码来显示可以实现的不同样式。

package stackoverflow;

import java.util.ArrayList;


public class MaxSumNode {

    /**
     * This is a partial implementation of the real TreeNode class, for local implementation only.
     * Remove when you have accedd to the real TreeNode class.
     */
    private static class TreeNode<T> {
        T                       data;
        ArrayList<TreeNode<T>>  children;

        public TreeNode(final T pData) {
            this.data = pData;
            children = new ArrayList<>();
        }

        public TreeNode<T> addChild(final TreeNode<T> pChild) {
            if (children == null) children = new ArrayList<>();
            children.add(pChild);
            return pChild; // used for builder syntax
        }
    }

    /**
     * This is our class that contains the maximum and some additional infos (the max Node itself for example).
     * This is private because it will not be used outside this class.
     */
    private static class CounterReference<T> {
        public int  nodeSum = 0;
        public T    node    = null;
        public CounterReference() {}
    }

    public enum Mode {
        ROOT_ONLY, ALL_LEVELS, ONLY_LEVEL_ONE, LEVEL_ONE_AND_BELOW
    }



    /**
     * Public method that returns calculations of a pre-set mode
     */
    public static CounterReference<TreeNode<Integer>> maxSumNode(final TreeNode<Integer> root) {
        return maxSumNode(root, Mode.ALL_LEVELS);
    }



    /**
     * Our only public 'intelligent' function, i.e. apart from the 2 simple helper functions.
     * Here we set up for the calculations, and decide what range we actually want to consider in out calculations.
     */
    public static CounterReference<TreeNode<Integer>> maxSumNode(final TreeNode<Integer> root, final Mode pMode) {
        final CounterReference<TreeNode<Integer>> cr = new CounterReference<>();

        // 4 different cases, depending on what you need. select ONE of those, comment out the rest
        switch (pMode) {
            case ROOT_ONLY: { // case 1: this case ONLY checks the root (level-0) element
                checkNode(root, cr, false);
                break;
            }
            case ALL_LEVELS: { // case 2: this case checks ALL elements, on ANY level
                checkNode(root, cr, true);
                break;
            }
            case ONLY_LEVEL_ONE: { // case 3: this case only checks level-1 elements (no root element, no child-children
                if (root != null && root.children != null && root.children.size() > 0) {
                    for (final TreeNode<Integer> cs : root.children) {
                        checkNode(cs, cr, false);
                    }
                }
                break;
            }
            case LEVEL_ONE_AND_BELOW: { // case 4: this case checks level-1 elements and down wards, effectively leaving out the root element
                if (root != null && root.children != null && root.children.size() > 0) {
                    for (final TreeNode<Integer> cs : root.children) {
                        checkNode(cs, cr, true);
                    }
                }
                break;
            }
            default:
                throw new IllegalArgumentException("Unknown Mode '" + pMode + "'!");
        }

        return cr;
    }

    /**
     * This node checks given Node and updates CounterReference if needed.
     * This is private, because this method is only used by {@link #maxSumNode(TreeNode)} and will not be used outside this class
     */
    private static void checkNode(final TreeNode<Integer> pNode, final CounterReference<TreeNode<Integer>> pCR, final boolean pRecursive) {
        if (pNode == null) return;

        final int sum = getWeightOfNodeAndDirectChildren(pNode);
        // compare local result with global result
        if (sum > pCR.nodeSum) {
            // we found a new max, so update counter
            pCR.nodeSum = sum;
            pCR.node = pNode;
        }

        // maybe do a recursive check of children and sub-children and sub-sub-children etc
        if (pRecursive && pNode.children != null && pNode.children.size() > 0) {
            for (final TreeNode<Integer> childNode : pNode.children) {
                checkNode(childNode, pCR, pRecursive);
            }
        }
    }



    /*
     * Our helper methods, to make the above code easier
     */

    public static int getWeightOfNodeAndDirectChildren(final TreeNode<Integer> pNode) {
        if (pNode == null) return 0;
        if (pNode.data == null) return 0;

        int sum = 0;
        sum += getWeightOfNode(pNode);
        if (pNode.children != null && pNode.children.size() > 0) {
            for (final TreeNode<Integer> childNode : pNode.children) {
                sum += getWeightOfNode(childNode);
            }
        }

        return sum;
    }

    public static int getWeightOfNode(final TreeNode<Integer> root) {
        if (root == null) return 0;
        if (root.data == null) return 0;
        return root.data.intValue();
    }



    /**
     * Our test method
     */

    public static void main(final String[] args) {
        final TreeNode<Integer> root = new TreeNode<>(Integer.valueOf(3));
        root.addChild(new TreeNode<>(Integer.valueOf(5)));

        final TreeNode<Integer> right = root.addChild(new TreeNode<>(Integer.valueOf(7)));
        right.addChild(new TreeNode<>(Integer.valueOf(13)));
        final TreeNode<Integer> rightRight = right.addChild(new TreeNode<>(Integer.valueOf(17)));
        right.addChild(new TreeNode<>(Integer.valueOf(19)));

        rightRight.addChild(new TreeNode<>(Integer.valueOf(23)));
        rightRight.addChild(new TreeNode<>(Integer.valueOf(29)));

        final TreeNode<Integer> left = root.addChild(new TreeNode<>(Integer.valueOf(11)));
        left.addChild(new TreeNode<>(Integer.valueOf(31)));

        final TreeNode<Integer> leftLeft = left.addChild(new TreeNode<>(Integer.valueOf(37)));
        leftLeft.addChild(new TreeNode<>(Integer.valueOf(41)));
        leftLeft.addChild(new TreeNode<>(Integer.valueOf(43)));


        System.out.println("The tree:");
        printNode(root, 0);
        System.out.println();

        System.out.println("The calculation modes:");
        for (final Mode mode : Mode.values()) {
            System.out.println("\tMode: " + mode);
            final CounterReference<TreeNode<Integer>> result = maxSumNode(root, mode);
            if (result == null || result.node == null) {
                System.out.println("\n\n0.o NOO!11!! We do NOT havea result!");
            } else {
                System.out.println("\t\tNode " + result.node.data.intValue() + " with max " + result.nodeSum);
            }
        }

        System.out.println("All done, exiting...");
    }



    private static void printNode(final TreeNode<Integer> pRoot, final int pDepth) {
        if (pRoot == null) return;

        for (int i = 0; i < pDepth; i++) {
            System.out.print("\t");
        }
        System.out.println(pRoot.data);

        if (pRoot.children != null && pRoot.children.size() > 0) {
            for (final TreeNode<Integer> c : pRoot.children) {
                printNode(c, pDepth + 1);
            }
        }
    }


}

//更新： 修复了内部checkNode()替换为的错误if ... return，if ... {}因为提前返回会阻止检查子级，即使他们可能在更深层次上找到新的最大值。