1080 Insufficient Nodes in Root to Leaf Paths

Posted on

Insufficient Nodes in Root to Leaf Paths

1
2
3
4
5
6
7
8
9
Given the root of a binary tree, consider all root to leaf paths: paths from the root to any leaf.  (A leaf is a node with no children.)

A node is insufficient if every such root to leaf path intersecting this node has sum strictly less than limit.

Delete all insufficient nodes simultaneously, and return the root of the resulting binary tree.
   1
 /    \
2      3
如果Limit=4，那么会只剩下[1,null,3];如果大于4，返回null

每个节点的所在的所有路径都小于Limit，那么就会删除这个节点。也就是说每个非叶子节点有两种状态，

  1. 需要删除。本来有儿子，如果该节点需要删除，那么两个（或者一个）儿子一定是删除的。

    1. root.left==root.right ==null

  2. 不需要删除，至少存在一个儿子不需要删除。

  3. 1
    2
    //==表示均为null
    root.left==root.right?null:root;

自底向上进行递归遍历。判断两个儿子的状态。

对于叶子节点，和limit想比较就行了。

1
2
3
if(root.left==null&&root.right==null){
	return root.val<limit?null:root;
}