^{<blockquote id="oiu9n"></blockquote>}

[LeetCode] 663. Equal Tree Partition

coordinate35 發(fā)布于2019-08-16 13:48 / 1528人閱讀

Problem

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 one edge on the tree.

Note:
The range of tree node value is in the range of [-100000, 100000].
1 <= n <= 10000

Solution

class Solution {
    Map map = new HashMap<>();
    public boolean checkEqualTree(TreeNode root) {
        if (root == null) return false;
        int total = getTotal(root);
        if (total%2 != 0) return false;
        if (total/2 == 0) return map.getOrDefault(total/2, 0) > 1;
        return map.containsKey(total/2);
    }
    private int getTotal(TreeNode root) {
        if (root == null) return 0;
        int total = root.val+getTotal(root.left)+getTotal(root.right);
        map.put(total, map.getOrDefault(total, 0)+1);
        return total;
    }
}

云服務器 GPU云服務器 equal LeetCode Partition LeetCode_String

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://www.ezyhdfw.cn/yun/72360.html

[Leetcode - Dynamic Programming] Partition Equal S

摘要：背包問題假設有個寶石，只有一個容量為的背包，且第個寶石所對應的重量和價值為和求裝哪些寶石可以獲得最大的價值收益思路我們將個寶石進行編號，尋找的狀態(tài)和狀態(tài)轉移方程。我們用表示將前個寶石裝到剩余容量為的背包中，那么久很容易得到狀態(tài)轉移方程了。 Partition Equal Subset Sum Given a non-empty array containing only posi...

qpal 2019-08-14 16:41 評論0 收藏0
leetcode416. Partition Equal Subset Sum

摘要：題目要求假設有一個全為正整數(shù)的非空數(shù)組，將其中的數(shù)字分為兩部分，確保兩部分數(shù)字的和相等。而這里的問題等價于，有個物品，每個物品承重為，問如何挑選物品，使得背包的承重搞好為所有物品重量和的一般。題目要求 Given a non-empty array containing only positive integers, find if the array can be partitio...

Caicloud 2019-08-16 15:10 評論0 收藏0
[LeetCode] 698. Partition to K Equal Sum Subsets

Problem Given an array of integers nums and a positive integer k, find whether its possible to divide this array into k non-empty subsets whose sums are all equal. Example 1:Input: nums = [4, 3, 2, 3,...

kuangcaibao 2019-08-16 13:41 評論0 收藏0
[LeetCode] 416. Partition Equal Subset Sum

Problem Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. Note:Each of the array ...

makeFoxPlay 2019-08-16 13:42 評論0 收藏0
leetcode 416 Partition Equal Subset Sum

摘要：如果是奇數(shù)的話，那一定是不滿足條件的，可以直接返回。如果是偶數(shù)，將除獲得我們要求的一個子數(shù)組元素的和。如何暫存我們計算的中間結果呢聲明一個長度為的布爾值數(shù)組。每個元素的布爾值代表著，數(shù)組中是否存在滿足加和為的元素序列。題目詳情 Given a non-empty array containing only positive integers, find if the array ca...

jsummer 2019-08-16 11:07 評論0 收藏0