删除给定值的叶子节点 图解题解

给一棵树和 target，要删掉哪些叶子

给你二叉树 root 和整数 target，把所有值等于 target 的叶子节点删掉。叶子，就是左右都没有孩子的节点。麻烦在删除会传染：删掉一个叶子后，它的父亲可能因为没了孩子变成新叶子，若新叶子值也等于 target 就接着删，直到删不动。题面例子 root=[10,20,30,20,null,20,40]、target=20。

见到值等于 target 就删，会把树删坏

见值等于 target 的节点就删，树很快散架：还挂着孩子的中间节点被删，它底下整棵子树就断链，答案就错了。所以『值等于 target』只是一半条件，另一半是它此刻必须是叶子，只有摘掉叶子才不牵连别人。剩下的问题就一个：判定一个节点时，怎么保证它的孩子已经删干净？

父亲删不删，得等孩子先删完

一个节点会不会变成叶子，取决于它的孩子删光了没有。所以判它之前得先把左右孩子处理完：递归扎进左右子树清干净，最后才回头轮到自己——先孩子、后父亲，这就是后序。等递归从孩子回来时，左右都空了、值又等于 target，这一刻它才是该删的叶子；只要还留着一个孩子，它就不是叶子，值撞上 target 也不动它。倒过来用前序先判父亲，孩子还没删，连锁的新叶子就漏了。

每个节点递归里做三步、返回一个结果

递归函数 removeLeafNodes(root, target) 分三步。边界：节点为空返回空。接着把左右孩子交给递归，注意把返回值接回去——root.left = removeLeafNodes(root.left, target)、root.right 同理，孩子被删时返回的空就接到 root.left 上。最后判自己：root.left 和 root.right 都空、且 root.val 等于 target，返回空把自己删掉，否则返回 root。

拿题面这棵树，从底下的叶子删起

根 10 左孩子 20、右孩子 30；左边的 20 底下还挂着一个 20；右边的 30 底下挂着 20 和 40。后序从 10 先钻左子树：左孩子 20 还有孩子先放着，到最底下的 20，左右皆空、值 20，命中删掉。

回到父亲 20，左孩子刚被置空、右孩子本就空，值又是 20，自己也成叶子被删——这就是连锁，底下删完正好轮到它。左枝向根返回空。右子树：30 的左孩子 20 是叶子且等于 20，删；右孩子 40 是叶子但 40 不等于 20，保留。回到 30 还留着 40、根 10 还留着 30，都不是叶子，保留。结果 [10,null,30,null,40]，正是题面输出。

接回返回值这步漏了，连锁就断了

最隐蔽的坑是递归后忘了把返回值接回孩子指针，只写 removeLeafNodes(root.left, target) 不赋回 root.left。孩子删了但父亲指针还指着它，连锁就断了。复杂度上后序每个节点访问一次，时间 O(n)；递归栈深度是树高 h，最坏 O(n)、平衡 O(log n)，空间 O(h)。[20,20,20]、target=20 会从底下一路连锁删到根，返回空树。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def removeLeafNodes(
        self, root: Optional[TreeNode], target: int
    ) -> Optional[TreeNode]:
        if root is None:
            return None
        root.left = self.removeLeafNodes(root.left, target)
        root.right = self.removeLeafNodes(root.right, target)
        if root.left is None and root.right is None and root.val == target:
            return None
        return root

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* removeLeafNodes(TreeNode* root, int target) {
        if (!root) {
            return nullptr;
        }
        root->left = removeLeafNodes(root->left, target);
        root->right = removeLeafNodes(root->right, target);
        if (!root->left && !root->right && root->val == target) {
            return nullptr;
        }
        return root;
    }
};

Java

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
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.left == null && root.right == null && root.val == target) {
            return null;
        }
        return root;
    }
}