LeetCode 1325. 删除给定值的叶子节点

Categories:

题目描述
思路分析
1. 解法一：后序遍历剪枝（推荐）
相似题目

题目描述

✅ 1325. 删除给定值的叶子节点

思路分析

解法一：后序遍历剪枝（推荐）

核心思路：

后序遍历先处理子树，得到剪枝后的左右子树。

若当前节点变成叶子且值等于目标，则删除该节点（返回 null）。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数。

空间复杂度：O(h)，其中 h 表示树高。

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

func removeLeafNodes(root *TreeNode, target int) *TreeNode {
	if root == nil {
		return nil
	}

	root.Left = removeLeafNodes(root.Left, target)
	root.Right = removeLeafNodes(root.Right, target)

	if root.Left == nil && root.Right == nil && root.Val == target {
		return nil
	}
	return root
}

相似题目

题目	难度	考察点
814. 二叉树剪枝	中等	后序遍历
1325. 删除给定值的叶子节点	中等	后序遍历
669. 修剪二叉搜索树	中等	递归
450. 删除二叉搜索树中的节点	中等	递归
1110. 删点成林	中等	递归
404. 左叶子之和	简单	递归

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/32266343