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

2. 解题

• 自底向上求得每个节点的子树和，更新于节点的 val
• 遍历检查+剪枝，共计2次遍历
• 实际上就是问这棵二叉树是否存在一棵真子树，其节点和等于总节点和的一半。可以两遍DFS，第一遍算出整棵树的节点和，第二遍查看是否有某棵子树的节点和恰好等于整棵树节点和的一半。代码如下：、

public class Solution {
    
    private boolean res;
    private int sum;
    
    public boolean checkEqualTree(TreeNode root) {
        sum = dfs(root, root);
        
        if (sum % 2 != 0) {
            return false;
        }
        
        // 将答案初始化为false
        res = false;
        
        dfs(root, root);
        return res;
    }
    
    // 返回cur为根的子树的节点和
    private int dfs(TreeNode cur, TreeNode root) {
        if (cur == null) {
            return 0;
        }
        
        int left = dfs(cur.left, root), right = dfs(cur.right, root);
        if ((left + right + cur.val) * 2 == sum && cur != root) {
            res = true;
        }
        
        return left + right + cur.val;
    }
}

class TreeNode {
    int val;
    TreeNode left, right;
    
    public TreeNode(int val) {
        this.val = val;
    }
}

 方法二:

class Solution {
    Map<Integer, Integer> 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;
    }
}