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

作者：掘金安东尼

2022 年 8 月 16 日
中国台湾
本文字数：628 字
阅读完需：约 2 分钟

清明假期第 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;};