题目地址：

https://leetcode.com/problems/delete-leaves-with-a-given-value/

删除二叉树中值为target的叶子节点。如果删除叶子后，新的叶子节点值也为target，则也要删除。返回删除后的树根。二叉树的后序遍历。先删除左子树中值为target的叶子节点，再删除右子树中值为target的叶子节点，最后如果根节点值为target并且左右子树都为空，那么就把根也删掉。代码如下：

public class Solution {
    public TreeNode removeLeafNodes(TreeNode root, int target) {
        if (root == null) {
            return null;
        }
        
        root.left = removeLeafNodes(root.left, target);
        root.right = removeLeafNodes(root.right, target);
    
        if (root.val == target && root.left == null && root.right == null) {
            return null;
        }
        
        return root;
    }
}

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) {
        val = x;
    }
}

时间复杂度$O(n)$O(n)，空间$O(h)$O(h)。

算法正确性证明：
对树的节点个数做归纳。如果树为空，成立。假设树有$n$n个节点，那么其左右子树的节点个数严格小于$n$n，由归纳法，左右子树的叶子节点值为target的已经删除完毕。接下来，如果树根自己成为了叶子节点，就会返回null，所以此时根节点也会被删掉。结论也成立。

• 点赞
• 收藏
• 分享
• • 文章举报

edWard的算法世界 发布了94 篇原创文章 · 获赞 0 · 访问量 1693 私信 关注