跳到主要内容

剑指 Offer II 047.二叉树剪枝

· 阅读需 2 分钟

1、题干​

给定一个二叉树 根节点 root ，树的每个节点的值要么是 0，要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。

节点 node 的子树为 node 本身，以及所有 node 的后代。

 

示例 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]
解释:


 

提示:

  • 二叉树的节点个数的范围是 [1,200]
  • 二叉树节点的值只会是 0 或 1

 

注意：本题与主站 814 题相同：https://leetcode-cn.com/problems/binary-tree-pruning/

执行结果​

1.png

解题思路​

总体思路：使用DFS递归遍历树的节点，递归过程中把值为0的叶子节点逐个剪除，就能得到剪枝后的二叉树。

代码​

var pruneTree = function (root) {
    function dfs(node) {
        if (!node) return;
        if (dfs(node.left)) node.left = null;
        if (dfs(node.right)) node.right = null;
        if (node.val === 0 && !node.left && !node.right) return true;
    }
    return dfs(root) ? null : root;
};