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

这道题到底在问什么

输入

root=[10,20,30,20,null,20,40], target=20

输出

[10,null,30,null,40]

输入

root=[20,20,20], target=20

输出

[](空树)

最优解：一步一步想明白

1. 3记牢一句:先把左右孩子递归删完,再看自己。只有自己当前是叶子、且值等于 target 才删。删除是自底向上连锁的,下面每一帧都在套这条规则。
2. 4target = 20,三个 20 待处理先看清这棵树。根是 10,它的左孩子是 20、右孩子是 30。左边那个 20 下面还挂着一个 20;右边的 30 下面挂着一个 20 和一个 40。target 等于 20,所以图里三个值为 20 的节点都是潜在的删除对象,但能不能删要看它当时是不是叶子。
3. 5叶子 = 左枝底 20 / 右枝 20 / 右枝 40紫色标出来的是这一刻真正的叶子,也就是没有孩子的节点:左枝最底下的 20、右枝下面的 20、还有右枝下面的 40。删除只从叶子开始。中间的 10、20、30 现在都还有孩子,暂时动不了,得等孩子处理完再说。
4. 6当前在根 10,先去左子树后序遍历从根 10 出发,但根要不要删,得等它的左右子树全部处理完才知道,所以现在先不判根,顺着左孩子一路往下钻。记住后序的精神:先孩子,后自己。
5. 7当前在左枝的 20,继续向下走到根的左孩子,这个 20。它下面还挂着一个 20,所以它现在不是叶子,还不能判。继续往它的左孩子钻下去,把底层先处理掉。
6. 8当前在左枝底 20,它没有孩子钻到最底下这个 20。它左右都没有孩子,到头了。这就是一个叶子,可以开始判定它该不该删。
7. 9叶子 + 值 20 等于 target判定这个叶子:它确实没有孩子,而且值是 20,正好等于 target。两个条件都满足,该删。下一帧就把它标红删掉。
8. 10删除左枝底 20,返回空给父亲左枝最底的 20 被删除,标红。在代码里删除不是真的抹掉内存,而是让它的父亲指向它的那根指针被置成空。这个空值会作为递归结果返回给它的父亲,也就是上面那个 20。
9. 11左孩子已置空,右孩子本就空回到上面这个 20。它刚收到孩子返回的空值,左孩子指针断开了。而它的右孩子本来就是空的。于是现在它左右都没有孩子了,情况发生了变化。
10. 12左右都空,它现在是叶子,值 20 等于 target关键的一刻来了。这个 20 原本不是叶子,可它的左孩子被删后,它现在左右都空,自己升级成了新叶子。再看它的值,正好也是 20,等于 target。新叶子又命中目标值,按规则它也得删。
11. 13连锁:删了底层叶子,父亲也成叶子被删左枝这个 20 被删除,标红。这就是题目说的连锁删除:先删掉底层那个 20,它的父亲因此变成新叶子,而新叶子的值还是 20,于是父亲也跟着被删。一趟后序遍历里,这种连锁是顺着回溯自动发生的。它再向上返回一个空。
12. 14根的左子树处理完,转向右子树回到根 10。它的左孩子返回了空,于是根的左孩子指针也断开了,整条左枝就剩两个红色的已删节点。根自己先别急着判,它还有右子树没处理。现在转向右边的 30。
13. 15当前在 30,继续向下走到根的右孩子,这个 30。它下面挂着一个 20 和一个 40,有孩子,不是叶子,先不判。按后序规矩,继续往它的左孩子钻。
14. 16当前在右枝 20,它没有孩子钻到 30 的左孩子,这个 20。它左右都没有孩子,又是一个叶子,可以判了。
15. 17叶子 + 值 20 等于 target判定这个叶子:没有孩子,值是 20,等于 target,两个条件都满足,该删。
16. 18删除右枝 20,返回空给 3030 的左孩子这个 20 被删除,标红,向 30 返回空。注意这次和左边不一样:30 的右边还有别的孩子,所以 30 不一定会变成叶子,等右孩子处理完再看。
17. 19当前在 40,它没有孩子回到 30,处理它的右孩子,这个 40。它左右都没有孩子,是个叶子,开始判定。
18. 20值 40 不等于 20,保留,变绿判定这个 40:它确实是叶子,可是它的值是 40,不等于 target 20。规则要求值等于 target 才删,所以它保留,标绿。它向 30 返回的是它自己,不是空。
19. 21左孩子空,右孩子 40 还在,30 有孩子回到 30 做后序判定。它的左孩子被删后是空的,但右孩子 40 保留了下来,所以 30 此刻仍然有孩子,它根本不是叶子。不是叶子就不删,哪怕值碰巧等于 target 也不删,因为删除只针对叶子。30 保留,标绿,向根返回它自己。
20. 22左孩子空,右孩子 30 还在,根有孩子最后回到根 10 做后序判定。它的左子树整条被删光了,左孩子是空的,但右孩子 30 保留着,所以根仍然有孩子,不是叶子,保留。再说根的值是 10 也不等于 target。根标绿,整棵树处理完毕。
21. 23结果 [10,null,30,null,40]收工。绿色的是保留下来的节点:根 10、它的右孩子 30、以及 30 的右孩子 40。红色的三个 20 全被删掉了。按层序写出来,结果就是 [10,null,30,null,40],根的左孩子位置是空。
22. 24左枝底 20 被删 → 左枝 20 变叶被删再回放一下最精彩的连锁:左枝最底的 20 先作为叶子被删,它的父亲那个 20 因此失去全部孩子、升级成新叶子,新叶子值还是 20,于是它也被删。这条自底向上的连锁,正是这道题区别于普通叶子删除的核心,而后序遍历天然就把这件事一次办妥。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问