📃 题目描述

题目链接：

• 剑指 Offer II 047. 二叉树剪枝 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 814. 二叉树剪枝 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

🔔 解题思路

理清题意，如果一棵子树上所有节点的值都为 0，那么删除这棵子树

也就是说，如果一个节点可以被删除，那么它的子树的所有节点都可以被删除。

由此发现，后序遍历最适合用来解决这个问题。

如果用后序遍历的顺序遍历到某个节点，那么它的左右子树的节点一定已经遍历（修剪）过了。

每遍历到一个节点，就要确定它是否有左右子树，如果左右子树都是空的，并且节点的值是 0，那么也就可以删除这个节点。

弄清楚递归函数的返回值能够帮助理解

TreeNode pruneTree(root) 表示：修剪以 root 为根节点的子树，然后返回修剪后的根节点

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 && root.val == 0) {
            return null;
            // 或者 root = null;
        }

        return root;
    }
}

画了一个图帮助理解：

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：