We are given the head node root of a binary tree, where additionally every node's value is either a 0 or a 1.
Return the same tree where every subtree (of the given tree) not containing a 1 has been removed.
(Recall that the subtree of a node X is X, plus every node that is a descendant of X.)
Example 1:Input: [1,null,0,0,1]Output: [1,null,0,null,1] Explanation: Only the red nodes satisfy the property "every subtree not containing a 1".The diagram on the right represents the answer.
Example 2: Input: [1,0,1,0,0,0,1]Output: [1,null,1,null,1]
Example 3: Input: [1,1,0,1,1,0,1,0]Output: [1,1,0,1,1,null,1]
Note: - The binary tree will have at most
100 nodes. - The value of each node will only be
0or1.
分析：这个题目的关键是找到如何判断子树全是0。很自然的想到用DFS函数去深度遍历，并且DFS应该设置为boolean类型，递归终止的条件是root==null，如果某个node，node.left==null，node.right==null并且node.val=0，那么就把这个node设为null。代码如下：
1 class Solution { 2 public TreeNode pruneTree(TreeNode root) { 3 dfs(root); 4 return root; 5 } 6 private boolean dfs(TreeNode root){ 7 //下面的代码完成对叶子节点的判断 8 if ( root == null ) return true; 9 boolean left = dfs(root.left);10 boolean right = dfs(root.right);11 if ( left && right && root.val == 0 ) return true;12 13 //下面的代码完成对叶子节点父节点的操作14 if ( left ) root.left=null;15 if ( right ) root.right=null;16 17 //如果叶子节点不满足上面的条件，就返回false18 return false;19 }20 } 从上面的代码可以清晰的看到DFS的三层架构，第一层要对当前节点进行判断，也就是递归结束的标志；第二层是操作层，当条件满足时要进行的操作；第三层就是当当前节点条件不满足时返回值。要注意在深度搜索中，都是从叶子节点向上搜索。
运行时间1ms，深搜确实是面对Tree问题的第一选择。
第二种思路，参考了其他人提交的代码，也可以优化第一种方法，不用boolean记录每个节点的情况。反而可读性更强，代码如下：
1 class Solution { 2 public TreeNode pruneTree(TreeNode root) { 3 return helper(root); 4 } 5 private TreeNode helper(TreeNode root) { 6 if ( root == null ) return null; 7 root.left = helper(root.left); 8 root.right = helper(root.right); 9 if ( root.left == null && root.right == null && root.val == 0 ) return null;10 return root;11 }12 } 同样的1ms时间，这个代码可读性更强，更好理解。