자바 알고리즘 시리즈 12 - 이 진 트 리 의 최대 하위 트 리 와

/**
     *      
     * @return              
     */
    public static BITNode constructTree(){
        BITNode root = new BITNode();
        BITNode node1 = new BITNode();
        BITNode node2 = new BITNode();
        BITNode node3 = new BITNode();
        BITNode node4 = new BITNode();
        root.data = 6;
        node1.data = 3;
        node2.data = 7;
        node3.data = 1;
        node4.data = 9;
        root.lchild = node1;
        root.rchild = node2;
        node1.lchild = node3;
        node1.rchild = node4;
        node2.lchild = node2.rchild = node3.lchild = node3.rchild = node4.lchild = node4.rchild = null;
        return root;
    }

/**
     *      
     * @param root    
     * @param maxRoot         
     * @return  root            
     */
    public static int findMaxSubTree(BITNode root,BITNode maxRoot){
        if(root == null){
            return 0;
        }
        // root         
        int lMax = findMaxSubTree(root.lchild,maxRoot);
        // root         
        int rMax = findMaxSubTree(root.rchild,maxRoot);
        int sum = lMax + rMax + root.data;
        // root                  
        if(sum > maxSum){
            maxSum = sum;
            maxRoot.data = root.data;
        }
        return sum;
    }

public static void main(String[] args) {
        BITNode root = constructTree();
        BITNode maxRoot = new BITNode();
        findMaxSubTree(root,maxRoot);
        System.out.println("      ："+maxSum);
        System.out.println("        ："+maxRoot.data);
    }