一、題目大意
給出二叉樹的根節點 root，樹上每個節點都有一個不同的值，
如果節點值在 to_delete 中出現，我們就把該節點從樹上刪去，最后得到一個森林（一些不相交的樹構成的集合），
回傳森林中的每棵樹，你可以按任意順序組織答案，
示例 1：
輸入：root = [1,2,3,4,5,6,7], to_delete = [3,5]
輸出：[[1,2,null,4],[6],[7]]
示例 2：
輸入：root = [1,2,4,null,3], to_delete = [3]
輸出：[[1,2,4]]
提示：
-
樹中的節點數最大為 1000，
-
每個節點都有一個介于 1 到 1000 之間的值，且各不相同，
-
to_delete.length <= 1000
-
to_delete 包含一些從 1 到 1000、各不相同的值，
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/delete-nodes-and-return-forest
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
二、解題思路
給一棵二叉樹，每個節點值均不同，洗掉一些節點，由于洗掉非葉子節點會使原來的二叉樹斷開，從而會形成從棵二叉樹，形成一片森林，回傳森林中所有二叉樹的根節點，
二叉樹的題首先想到用遞回，遞回方法傳遞4個引數，當前節點；是否是根節點（如果是根節點、且存在左右子樹才會形成新樹）；再傳遞一個hashset用來存盤要洗掉的節點，達到常資料級搜索；還有一個保存結果的list，
在遞回函式中，如果節點為慷訓傳null，定義亦是deleted來保存當前節點值是否在hashset中，若是根節點且不需要被洗掉，則將節點加入回傳結果list中，然后將左子節點賦值為對左子節點呼叫遞回函式的回傳值，右子節點賦值為對右子節點呼叫遞回函式的回傳值，最后判斷當前節點是否被洗掉了，如果是的話回傳空，否則回傳當前指標，這樣的話每棵樹的根節點都在遞回程序中存入結果list中了，
三、解題方法
3.1 Java實作
/**
* 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 Solution {
public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
List<TreeNode> ans = new ArrayList<>();
Set<Integer> set = new HashSet<>();
for (int tmp : to_delete) {
set.add(tmp);
}
helper(root, true, set, ans);
return ans;
}
TreeNode helper(TreeNode node, boolean isRoot, Set<Integer> set, List<TreeNode> ans) {
if (node == null) {
return null;
}
boolean deleted = set.contains(node.val);
if (isRoot && !deleted) {
ans.add(node);
}
node.left = helper(node.left, deleted, set, ans);
node.right = helper(node.right, deleted, set, ans);
return deleted ? null : node;
}
}
四、總結小記
- 2022/9/14 作業接踵而至
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/508101.html
標籤：其他