`
standalone
  • 浏览: 611471 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

find the subtree with max sum

    博客分类:
  • java
阅读更多
Problem:
Given a binary tree, each node has an integer value attached (can be negative), write code to find the subtree with the max sum.

My solution:
Basically this is a recursive problem, for each subtree result, you should remember its maxSum and corresponding root node. So I use a struct SubTreeResult to remember all such info.

Note: The code I pasted here is not tested sufficiently, so don't take it as correct solution unless you verify it yourself.

package alg;

import java.util.ArrayList;

public class MaxSumTree {
    
    class Node {
        int value;
        Node left, right;
        Node(int v, Node l, Node r){
            value = v;
            left = l;
            right = r;
        }
    }
    
    class SubTreeResult {
        Node subTreeRoot, maxSumNode;
        int sum, maxSum;
        SubTreeResult(Node r, Node maxNode, int maxSum, int sum){
            this.subTreeRoot = r;
            this.maxSumNode = maxNode;
            this.sum = sum;
            this.maxSum = maxSum;
        }
    }
    
    public SubTreeResult findMaxSubTree(Node r){
        SubTreeResult leftResult = null, rightResult = null, result = null;    
        if(r.left != null){
            leftResult = findMaxSubTree(r.left);
        }
        if(r.right != null){
            rightResult = findMaxSubTree(r.right);
        }
        
        if(leftResult != null && rightResult != null){
            int sum = r.value + leftResult.sum + rightResult.sum;
            if(leftResult.maxSum >= rightResult.maxSum){                
                if(sum >= leftResult.maxSum){
                    result = new SubTreeResult(r, r, sum, sum); 
                }else {
                    result = new SubTreeResult(r, leftResult.maxSumNode, leftResult.maxSum, sum);
                }
            }else {
                if(sum >= rightResult.maxSum){
                    result = new SubTreeResult(r, r, sum, sum); 
                }else {
                    result = new SubTreeResult(r, rightResult.maxSumNode, rightResult.maxSum, sum);
                }                
            }
        }else if(leftResult != null){
            int sum = r.value + leftResult.sum;
                            
            if(sum >= leftResult.maxSum){
                result = new SubTreeResult(r, r, sum, sum); 
            }else {
                result = new SubTreeResult(r, leftResult.maxSumNode, leftResult.maxSum, sum);
            }            
        }else if(rightResult != null){
            int sum = r.value + rightResult.sum;
            if(sum >= rightResult.maxSum){
                result = new SubTreeResult(r, r, sum, sum); 
            }else {
                result = new SubTreeResult(r, rightResult.maxSumNode, rightResult.maxSum, sum);
            }            
        }else {
            result = new SubTreeResult(r, r, r.value, r.value);
        }
        return result;
    }
    
    public Node buildBinaryTree(ArrayList<Integer> list){
        int size = list.size();
        if(size == 0) return null;
        
        Node [] nodes = new Node[size];
        for(int i = 0; i< size; i++){
            int number = list.get(i);
            nodes[i] = new Node(number, null, null);
            int idx = i;
            if(i%2 == 0){
                idx = i - 1;
            }
            if(idx > 0){
                idx /= 2;
                if(i%2 == 0){
                    nodes[idx].right = nodes[i];
                }else {
                    nodes[idx].left = nodes[i];
                }
            }
        }        
        return nodes[0];        
    }
    
    public void printTree(Node root){
        if(root != null){
            System.out.println(root.value);
            if(root.left != null)
                printTree(root.left);
            if(root.right != null)
                printTree(root.right);
        }
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MaxSumTree mst = new MaxSumTree();
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(3);
        list.add(-4);
        list.add(2);
        list.add(7);
        list.add(-5);
        list.add(9);
        list.add(-8);
        list.add(-2);
        list.add(5);
        list.add(20);
        list.add(100);
        list.add(-30);
        list.add(-150);
        
        Node root = mst.buildBinaryTree(list);
        mst.printTree(root);
        SubTreeResult str = mst.findMaxSubTree(root);
        System.out.println("max sum subtree root:" + str.maxSumNode.value + ", max sub:" + str.maxSum);
    }

}

分享到:
评论

相关推荐

    java-leetcode题解之Most Frequent Subtree Sum.java

    java java_leetcode题解之Most Frequent Subtree Sum.java

    为什么使用Git Subtree

    Git Subtree是一种在版本控制系统Git中使用的技术,它允许将一个仓库中的分支或提交作为一个子目录合并到另一个仓库中。相对于Submodule,Git Subtree是另一种管理子模块的方法。Git Submodule是Git官方推出的一个...

    SubTree Mining

    在IT领域,数据挖掘是至关重要的一个分支,而“SubTree Mining”则专注于发现数据库中频繁出现的子树模式。这个程序是用Java语言编写的,它提供了一种有效的方法来处理树形结构数据,特别是在数据库中寻找重复或频繁...

    CBST.rar_The Keys_bst

    The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than or equal to the node's key. Both the left ...

    数据结构和算法面试最新100题

    maxSum = std::max(maxSum, currentSum); } return maxSum; } ``` #### 四、在二元树中找出和为某一值的所有路径 **知识点概述:** 本题考查如何通过递归方式遍历二叉树并寻找符合条件的路径。 **实现思路:*...

    陈越、何钦铭-数据结构作业16:Complete Binary Search Tree完全二叉搜索树

    The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than or equal to the node's key. Both the left and ...

    Largest Common SubTree 公共子树查找算法

    最大公共子树(Maximal Common Subtree, MCST)查找问题是计算机科学领域中的一个重要课题,它涉及到多种数据结构和算法设计,尤其在计算机设计、符号计算、程序设计理论、生物信息学、网络及半结构化数据挖掘等领域...

    git-subtree-2.31.1-2.el8.x86_64.rpm

    官方离线安装包,测试可用。使用rpm -ivh [rpm完整包名] 进行安装

    subtree-sample-common-repo:子树示例的通用存储库

    例如,如果通用代码库是“common”,你可能会运行`git subtree add --prefix=src/common subtree-sample-common-repo master`,将“subtree-sample-common-repo”的master分支内容添加到项目中的“src/common”目录...

    git-subtree-2.31.1-2.el8.aarch64.rpm

    官方离线安装包,测试可用。使用rpm -ivh [rpm完整包名] 进行安装

    git-subtree-2.27.0-1.el8.ppc64le.rpm

    离线安装包,亲测可用

    Indexing for Subtree Similarity-Search using Edit Distance

    树编辑距离用于子树相似性搜索的索引技术 在信息技术领域,尤其是在处理结构化数据如XML文档和生物信息学中的RNA二级结构时,树结构数据模型的相似性搜索是一个基础且重要的问题。Sara Cohen在其2013年发表于SIGMOD...

    git-subtree-2.27.0-1.el8.x86_64.rpm

    离线安装包,亲测可用

    lerna-subtree-publish:使用git-subtree用于packge存储库的lerna的包装器

    Lerna-subtree-发布你需要什么用于具有以下设置的 mono存储库: lerna.jsonpackage.jsonsubtrees.jsonpackages/ a/ package.json b/ package.json通常,每个程序包都位于按配置的单独子存储库中。 我们还假定您要对...

    acpi控制笔记本风扇转速

    Fixed a problem with the Global Lock where the lock could appear to be obtained before it is actually obtained. The global lock semaphore was inadvertently created with one unit instead of zero units....

    Codeforces 1324 F. Maximum White Subtree (树形dp) /详解

    Maximum White Subtree time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output You are given a tree consisting of n vertices. A tree is a connected ...

    intl, [READ ONLY] Subtree组件的子树拆分.zip

    intl, [READ ONLY] Subtree组件的子树拆分 组件用于C 扩展的PHP替换层,它还提供对ICU库的本地化数据的访问。替换层仅限于区域设置"en"。 如果要使用其他语言环境,则应使用 [install the intl PHP extension] 0 。...

Global site tag (gtag.js) - Google Analytics