814. 二叉树剪枝 : 简单递归运用题

814. 二叉树剪枝 : 简单递归运用题

题目描述

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

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

节点 ​​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]

提示：

递归

不失一般性的考虑任意节点作为入参该如何处理：我们可以递归处理左右子树，并将新左右子树重新赋值给 ​​root​​​。由于当前节点 ​​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

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

最后

这是我们「刷穿 LeetCode」系列文章的第 ​​No.814​​ 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：​​github.com/SharingSour…​​ 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。