1. 题目描述
给定二叉树根结点 root ，此外树的每个结点的值要么是 0，要么是 1。
返回移除了所有不包含 1 的子树的原二叉树。
( 节点 X 的子树为 X 本身，以及所有 X 的后代。)
示例1:
输入: [1,null,0,0,1]
输出: [1,null,0,null,1]
解释:
只有红色节点满足条件“所有不包含 1 的子树”。
右图为返回的答案。
示例2:
输入: [1,0,1,0,0,0,1]
输出: [1,null,1,null,1]
示例3:
输入: [1,1,0,1,1,0,1,0]
输出: [1,1,0,1,1,null,1]
给定的二叉树最多有 100 个节点。
每个节点的值只会为 0 或 1 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-pruning
2. 解题说明
递归：
我们可以使用递归来解决这个问题。我们用 containsOne(node) 函数来判断以 node 为根的子树中是否包含 1，其不包含 1 当且仅当以 node 的左右孩子为根的子树均不包含 1，并且 node 节点本身的值也不为 1。
如果 node 的左右孩子为根的子树不包含 1，那我们就需要把对应的指针置为空。例如当 node 的左孩子为根的子树不包含 1 时，我们将 node.left 置为 null。
在递归结束之后，如果整颗二叉树都不包含 1，那么我们返回 null，否则我们返回原来的根节点。
class Solution {
public TreeNode pruneTree(TreeNode root) {
return containsOne(root) ? root : null;
}
public boolean containsOne(TreeNode node) {
if (node == null) return false;
boolean a1 = containsOne(node.left);
boolean a2 = containsOne(node.right);
if (!a1) node.left = null;
if (!a2) node.right = null;
return node.val == 1 || a1 || a2;
}
}
3. 压弹栈的伪代码展示
该算法题目，本身算不上复杂。 不过压弹栈过程表示起来比较复杂，容易混淆。
以下为伪代码示意图。
为了方便示意，将示例2:
输入: [1,0,1,0,0,0,1]
二叉树各个节点，从上至下，逐层 依次表示为A B C D E F G
程序示例如下：
首先从A 开始，到B，然后依次遍历B 的左右子树，依次按层次顺序向下执行。
递归的核心点就在于：遍历完E的右子树后，跳转至B的同级节点C继续执行。
