663. Equal Tree Partition 能否把树均分为求和相等的两半

时间:2021-08-19 08:07:49

[抄题]:

Given a binary tree with n nodes, your task is to check if it's possible to partition the tree to two trees which have the equal sum of values after removing exactly one edge on the original tree.

Example 1:

Input:
5
/ \
10 10
/ \
2 3 Output: True
Explanation:
5
/
10 Sum: 15 10
/ \
2 3 Sum: 15

Example 2:

Input:
1
/ \
2 10
/ \
2 20 Output: False
Explanation: You can't split the tree into two trees with equal sum after removing exactly on

[暴力解法]:

时间分析:

空间分析:

[优化后]:

时间分析:

空间分析:

[奇葩输出条件]:

[奇葩corner case]:

[思维问题]:

以为是传统的dc-路径求和,没想到是分成几个函数来做。完全没想到。

[英文数据结构或算法,为什么不用别的数据结构或算法]:

[一句话思路]:

getTotal(root.left) + getTotal(root.right) + root.val通过自定义的函数名来进行traverse

[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):

[画图]:

[一刷]:

  1. 先退出再expand, checkequal只要有一个true就直接退出了

[二刷]:

[三刷]:

[四刷]:

[五刷]:

[五分钟肉眼debug的结果]:

[总结]:

通过自定义的函数名来进行traverse,先退出再expand, checkequal只要有一个true就直接退出了 

[复杂度]:Time complexity: O(n) Space complexity: O(1)

[算法思想:迭代/递归/分治/贪心]:

[关键模板化代码]:

public long checkEqual(TreeNode root) {
//exit or expand
if (root == null || equal) return 0; long curSum = checkEqual(root.left) + checkEqual(root.right) + root.val;
if (curSum == targetSum - curSum) {
equal = true;
return 0;
}
return curSum;
}

[其他解法]:

[Follow Up]:

[LC给出的题目变变变]:

[代码风格] :

[是否头一次写此类driver funcion的代码] :

[潜台词] :

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
//initialiazation
boolean equal = false;
long targetSum = 0; public boolean checkEqualTree(TreeNode root) {
targetSum = getSum(root);
checkEqual(root);
return equal;
} public long getSum(TreeNode root) {
//exit or expand
if (root == null) return 0;
return getSum(root.left) + getSum(root.right) + root.val;
} public long checkEqual(TreeNode root) {
//exit or expand
if (root == null || equal) return 0; long curSum = checkEqual(root.left) + checkEqual(root.right) + root.val;
if (curSum == targetSum - curSum) {
equal = true;
return 0;
}
return curSum;
}
}

663. Equal Tree Partition 能否把树均分为求和相等的两半的更多相关文章

  1. [LeetCode] 663. Equal Tree Partition 划分等价树

    Given a binary tree with n nodes, your task is to check if it's possible to partition the tree to tw ...

  2. [LeetCode] Equal Tree Partition 划分等价树

    Given a binary tree with n nodes, your task is to check if it's possible to partition the tree to tw ...

  3. 【LeetCode】663. Equal Tree Partition 解题报告 (C++)

    作者: 负雪明烛 id: fuxuemingzhu 个人博客:http://fuxuemingzhu.cn/ 目录 题目描述 题目大意 解题方法 递归 日期 题目地址:https://leetcode ...

  4. [BZOJ3754]Tree之最小方差树

    3754: Tree之最小方差树 Time Limit: 20 Sec  Memory Limit: 256 MBSubmit: 402  Solved: 152[Submit][Status][Di ...

  5. [BZOJ3080]Minimum Variance Spanning Tree/[BZOJ3754]Tree之最小方差树

    [BZOJ3080]Minimum Variance Spanning Tree/[BZOJ3754]Tree之最小方差树 题目大意: 给定一个\(n(n\le50)\)个点,\(m(m\le1000 ...

  6. poj3321-Apple Tree(DFS序+树状数组)

    Apple Tree Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 36442   Accepted: 10894 Desc ...

  7. POJ.3321 Apple Tree ( DFS序 线段树 单点更新 区间求和)

    POJ.3321 Apple Tree ( DFS序 线段树 单点更新 区间求和) 题意分析 卡卡屋前有一株苹果树,每年秋天,树上长了许多苹果.卡卡很喜欢苹果.树上有N个节点,卡卡给他们编号1到N,根 ...

  8. CSU 1811: Tree Intersection(线段树启发式合并||map启发式合并)

    http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1811 题意:给出一棵树,每一个结点有一个颜色,然后依次删除树边,问每次删除树边之后,分开的两个 ...

  9. Count on a tree SPOJ 10628 主席树+LCA(树链剖分实现)(两种存图方式)

    Count on a tree SPOJ 10628 主席树+LCA(树链剖分实现)(两种存图方式) 题外话,这是我第40篇随笔,纪念一下.<( ̄︶ ̄)↗[GO!] 题意 是说有棵树,每个节点上 ...

随机推荐

  1. jQuery 2&period;0&period;3 源码分析Sizzle引擎 - 编译函数(大篇幅)

    声明:本文为原创文章,如需转载,请注明来源并保留原文链接Aaron,谢谢! 从Sizzle1.8开始,这是Sizzle的分界线了,引入了编译函数机制 网上基本没有资料细说这个东东的,sizzle引入这 ...

  2. 让IE7 IE8支持CSS3 background-size属性

    简介 CSS3 新增的 background-size 是一个很有用的属性,用于定义背景图片的尺寸,有了这个属性,你就可以任意指定背景图片的大小.其中最常用的值应该要数 cover 了,该值能让背景图 ...

  3. 高清SDI编码器&vert;上海视涛科技

    SDI编码器(E500)简介 SDI编码器(E500)是上海视涛科技出品的高性能SDI编码产品.该SDI编码器是上海视涛电子完全自主研发,并适用于各种SDI信号的编码采集及网络传输的专用硬件设备.可兼 ...

  4. 关于javaScript注册事件传递参数的浅析

    最近这半年作为一个java 程序员,我写的javaScript代码都快比java代码多了,前段时间是给某银行做一个柜员管控系统,在柜员授权这一块功能上,由于柜员的授权需要考虑各方面的因素,比如机构权限 ...

  5. chown

    chown 命令 用途:更改与文件关联的所有者或组 chown [ -f ] [ -h ] [ -R ] Owner [ :Group ] { File ... | Directory ... } c ...

  6. Vue 事件

    一.事件冒泡 方法一.使用event.cancelBubble = true来阻止冒泡 <div @click="show2()"> <input type=&q ...

  7. Java爬虫--Https绕过证书

    https网站服务器都是有证书的. 是由网站自己的服务器签发的,并不被浏览器或操作系统广泛接受. 在使用CloseableHttpClient时经常遇到证书错误(知乎的网站就是这样) 现在需要SSL绕 ...

  8. Linux shell编写端口扫描脚本

    Linux shell编写端口扫描脚本 需求: 扫描特定主机 扫描特定主机的特定端口 扫描特定网段 扫描特定网段中哪些主机开放了特定的端口 源码如下: #/bin/bash #该脚本用于对特定目标主机 ...

  9. springcloud的Turbine配置监控多个服务的一些坑&excl;&excl;&excl;&excl;InstanceMonitor&dollar;MisconfiguredHostException&comma;No message available&quot&semi;&comma;&quot&semi;path&quot&semi;&colon;&quot&semi;&sol;actuator&sol;hystrix&period;stream&comma;页面不显示服务或者一直loading

    踩了几个小时坑,使用仪表盘监控单个服务的时候很容易,但是一到多个服务,瞬间坑就来了,大概碰到下面三个: 1InstanceMonitor$MisconfiguredHostException, No ...

  10. C&num;中的基础数据类型

    一.C#有15个预定义类型,13个值类型,两个引用类型(string和object): 1.整型 int a=15; short a=15; 2.浮点类型 float a=12.9; double a ...