- 浏览: 611471 次
- 性别:
- 来自: 上海
文章分类
最新评论
-
月光杯:
问题解决了吗?
Exceptions in HDFS -
iostreamin:
神,好厉害,这是我找到的唯一可以ac的Java代码,厉害。
[leetcode] word ladder II -
standalone:
One answer I agree with:引用Whene ...
How many string objects are created? -
DiaoCow:
不错!,一开始对这些确实容易犯迷糊
erlang中的冒号 分号 和 句号 -
standalone:
Exception in thread "main& ...
one java interview question
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.
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); } }
发表评论
-
ssl 与 java 实例
2014-01-27 10:10 844http://www.iteye.com/topic/1125 ... -
Java NIO
2014-01-10 21:28 744看了这个java nio的教程,明白了什么是Selector. ... -
再谈Java的wait(), sleep(), notify()和notifyAll()
2013-07-25 10:59 1945一段时间不用java,这些概念就全混淆了,有必要彻底澄清一下, ... -
Why singleton is anti-pattern?
2013-07-03 10:12 912OO Test Other reasons? -
How to generate the serialVersionUID when you implement Serializable interface,j
2013-07-01 10:52 987http://docs.oracle.com/javase/6 ... -
Java Override的两个问题
2013-06-01 11:40 9891: 如果子类中的方法的参数是父类的方法的子类型,那么算不算o ... -
Java常用类API统计
2013-06-01 11:35 0String charAt(int) compareTo( ... -
How many string objects are created?
2013-06-01 10:18 1356This is a very common java inte ... -
使用Java的DelayQueue容易碰到的一个坑
2013-05-27 17:32 6785今天不忙,学习一下java.util.concurrent.D ... -
[leetcode] Balanced Binary Tree
2013-04-28 14:08 1615Check if a binary tree is balan ... -
[leetcode] find median of two sorted arrays
2013-04-26 10:55 1501http://leetcode.com/onlinejudge ... -
[leetcode] word ladder
2013-04-25 15:05 2309Q: Given two words (start and ... -
[leetcode] word ladder II
2013-04-15 07:35 12089http://leetcode.com/onlinejudge ... -
[leetcode] Count and Say
2013-04-12 14:05 2280http://leetcode.com/onlinejudge ... -
Date/Time处理函数总结 [To Do]
2013-04-12 10:46 708几种我所用到的用来处理日期,时间的函数总结。 Perl 1 ... -
[leetcode] Palindrome Partition
2013-04-12 10:25 1345http://leetcode.com/onlinejudge ... -
[leetcode] Palindrome Partitioning II
2013-04-11 16:45 1550http://leetcode.com/onlinejudge ... -
Profiling your Java code using Spring
2013-03-05 15:02 730Quite good article!!! http://w ... -
Java的Generics的几点限制
2012-12-28 15:00 4797参见 http://docs.oracle.com/ ... -
Overriding Method Using Parameter That is a Subclass?
2012-12-27 22:14 929参见 http://www.coderanch.com/t/3 ...
相关推荐
java java_leetcode题解之Most Frequent Subtree Sum.java
Git Subtree是一种在版本控制系统Git中使用的技术,它允许将一个仓库中的分支或提交作为一个子目录合并到另一个仓库中。相对于Submodule,Git Subtree是另一种管理子模块的方法。Git Submodule是Git官方推出的一个...
在IT领域,数据挖掘是至关重要的一个分支,而“SubTree Mining”则专注于发现数据库中频繁出现的子树模式。这个程序是用Java语言编写的,它提供了一种有效的方法来处理树形结构数据,特别是在数据库中寻找重复或频繁...
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 ...
maxSum = std::max(maxSum, currentSum); } return maxSum; } ``` #### 四、在二元树中找出和为某一值的所有路径 **知识点概述:** 本题考查如何通过递归方式遍历二叉树并寻找符合条件的路径。 **实现思路:*...
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 ...
最大公共子树(Maximal Common Subtree, MCST)查找问题是计算机科学领域中的一个重要课题,它涉及到多种数据结构和算法设计,尤其在计算机设计、符号计算、程序设计理论、生物信息学、网络及半结构化数据挖掘等领域...
官方离线安装包,测试可用。使用rpm -ivh [rpm完整包名] 进行安装
例如,如果通用代码库是“common”,你可能会运行`git subtree add --prefix=src/common subtree-sample-common-repo master`,将“subtree-sample-common-repo”的master分支内容添加到项目中的“src/common”目录...
官方离线安装包,测试可用。使用rpm -ivh [rpm完整包名] 进行安装
离线安装包,亲测可用
树编辑距离用于子树相似性搜索的索引技术 在信息技术领域,尤其是在处理结构化数据如XML文档和生物信息学中的RNA二级结构时,树结构数据模型的相似性搜索是一个基础且重要的问题。Sara Cohen在其2013年发表于SIGMOD...
离线安装包,亲测可用
Lerna-subtree-发布你需要什么用于具有以下设置的 mono存储库: lerna.jsonpackage.jsonsubtrees.jsonpackages/ a/ package.json b/ package.json通常,每个程序包都位于按配置的单独子存储库中。 我们还假定您要对...
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....
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组件的子树拆分 组件用于C 扩展的PHP替换层,它还提供对ICU库的本地化数据的访问。替换层仅限于区域设置"en"。 如果要使用其他语言环境,则应使用 [install the intl PHP extension] 0 。...