关于后端:814-二叉树剪枝-简单递归运用题

1次阅读

共计 1415 个字符，预计需要花费 4 分钟才能阅读完成。

这是 LeetCode 上的 814. 二叉树剪枝 ，难度为中等。

Tag :「二叉树」、「DFS」、「递归」

给你二叉树的根结点 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]

提醒：

树中节点的数目在范畴 $[1, 200]$ 内
Node.val 为 $0$ 或 $1$

依据题意，咱们将原函数 pruneTree 作为递归函数，递归函数的含意为「将入参 root 中的所有不蕴含 $1$ 的子树移除，并返回新树头结点」。

不失一般性的思考任意节点作为入参该如何解决：咱们能够递归解决左右子树，并将新左右子树从新赋值给 root。因为以后节点 root 的左右子树可能为空树，因而咱们要减少递归函数入参为空的边界解决。

当递归操作实现后，若左右节点任一值不为空（阐明以后节点 root 不为叶子节点），咱们能够间接返回 root，否则依据 root 的值是否为 $0$ 来决定返回空树还是 root 自身。

Java 代码：

class Solution {public TreeNode pruneTree(TreeNode root) {if (root == null) return null;
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if (root.left != null || root.right != null) return root;
        return root.val == 0 ? null : root;
    }
}

TypeScript 代码：

function pruneTree(root: TreeNode | null): TreeNode | null {if (root == null) return null
    root.left = pruneTree(root.left)
    root.right = pruneTree(root.right)
    if (root.left != null || root.right != null) return root
    return root.val == 0 ? null : root
};