春意盎然，适合“二叉树剪枝”

---

清明假期第 1 天，日日新更文继续 ^_^

天气正好，树木繁茂，不如来道二叉树的 —— 二叉树剪枝 题~🐶

题：

给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。

返回移除了所有不包含 1 的子树的原二叉树。

节点 node 的子树为 node 本身加上所有 node 的后代。

示例 1：

输入：root = [1,null,0,0,1]
输出：[1,null,0,null,1]
解释：
只有红色节点满足条件“所有不包含 1 的子树”。 右图为返回的答案。

示例 2：

输入：root = [1,0,1,0,0,0,1]
输出：[1,null,1,null,1]

示例 3：

输入：root = [1,1,0,1,1,0,1,0]
输出：[1,1,0,1,1,null,1]

【解题思路】

题目要求剪除二叉树中所有节点的值为 0 的子树，那么怎么知道当前二叉树所有节点的值为0，使用后序遍历无疑了； 递归只需要考虑当前节点需要做什么事情，当前节点能否被剪枝取决于左右子树及当前节点的值；

这道题的难点在于要一直剪枝，直到没有值为 0 的叶子节点为止，只有从后序遍历位置自底向上处理才能获得最高的效率。

【JS 实现】

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var pruneTree = function(root) {
  // 判断非空情况
  if (root == null) {
    return root;
  }
  root.left = pruneTree(root.left);
  root.right = pruneTree(root.right);
  // 当左右节点都为空且当前节点的值为0的情况下，即可剪枝
  if (!root.left && !root.right && root.val == 0) {
    return null;
  }
  return root;
};

【验证】

---

后序遍历+递归，简单实现，赞👍