题:
给你二叉树的根结点 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; };
【验证】
后序遍历+递归,简单实现,赞👍




