专栏首页Michael阿明学习之路LeetCode 663. 均匀树划分(树形DP)

LeetCode 663. 均匀树划分(树形DP)

1. 题目

给定一棵有 n 个结点的二叉树,你的任务是检查是否可以通过去掉树上的一条边将树分成两棵,且这两棵树结点之和相等。

样例 1:
输入:     
    5
   / \
  10 10
    /  \
   2   3
输出: True
解释: 
    5
   / 
  10
      
和: 15

   10
  /  \
 2    3

和: 15
 

样例 2:
输入:     
    1
   / \
  2  10
    /  \
   2   20
输出: False
解释: 无法通过移除一条树边将这棵树划分成结点之和相等的两棵子树。
 
注释 :
树上结点的权值范围 [-100000, 100000]。
1 <= n <= 10000

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/equal-tree-partition 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • 自底向上求得每个节点的子树和,更新于节点的 val
  • 遍历检查+剪枝,共计2次遍历
class Solution {
	bool found = false;
	int allsum;
public:
    bool checkEqualTree(TreeNode* root) {
    	allsum = sum(root);
        if(allsum&1) return false;//奇数不可分
    	check(root);
    	return found;
    }
    int sum(TreeNode* root)
    {
    	if(!root) return 0;
    	int l = sum(root->left);
    	int r = sum(root->right);
    	return root->val += l+r;
    }
    bool check(TreeNode* root)
    {
    	if(!root) return false;
        if(found) return true;
    	if(root->left && allsum == 2*root->left->val)
    		return found = true;
    	if(root->right && allsum == 2*root->right->val)
    		return found = true;
    	return check(root->left) || check(root->right);
    }
};

40 ms 31.9 MB

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指Offer - 面试题54. 二叉搜索树的第k大节点(二叉树循环遍历)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kd...

    Michael阿明
  • LeetCode 222. 完全二叉树的节点个数(二分查找)

    说明: 完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底...

    Michael阿明
  • 程序员面试金典 - 面试题 04.05. 合法二叉搜索树(中序遍历)

    Michael阿明
  • python中创建和遍历二叉树

    py3study
  • Linux工作目录切换命令

    心跳包
  • 剑指Offer - 面试题54. 二叉搜索树的第k大节点(二叉树循环遍历)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kd...

    Michael阿明
  • 利用rbd命令把 ceph pool 中的一个镜像导出

    查看镜像 [root@node1 ~]# rbd ls images a56330e7-79d7-4639-a68f-366ac344bfe2 eccfee07...

    院长技术
  • 浏览器环境检测

    本文是直接把seleniumpyppeteer 以及正常打开浏览器 的环境差异直接列出来

    爬虫
  • Cephfs的快照功能

    Cephfs的快照功能在官网都很少提及,因为即使开发了很多年,但是由于cephfs的复杂性,功能一直没能达到稳定,这里,只是介绍一下这个功能,怎么使用,并且建议...

    用户2772802
  • python中os. popen sy

    python调用Shell脚本或者是调用系统命令,有两种方法: os.system(cmd)或os.popen(cmd),前者返回值是脚本的退出状态码,正确会返...

    py3study

扫码关注云+社区

领取腾讯云代金券