LeetCode 1110. Delete Nodes And Return Forest(java)

2667 단어 Tree
Given the root of a binary tree, each node in the tree has a distinct value.
After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).
Return the roots of the trees in the remaining forest. You may return the result in any order.
Example 1:
Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

Constraints:
The number of nodes in the given tree is at most 1000. Each node has a distinct value between 1 and 1000. to_delete.length <= 1000 to_delete contains distinct values between 1 and 1000.
사고: result list 에서 모든 루트 노드 를 옮 겨 다 니 며 삭제 할 node 와 부모 노드 를 찾 습 니 다. 부모 노드 의 하위 노드 node 를 null 로 설정 하고 node 노드 의 좌우 아 이 를 추가 합 니 다 (null 이 아니라면) result list 에 들 어 갑 니 다.
class Solution {
    public List delNodes(TreeNode root, int[] to_delete) {
        List res = new ArrayList<>();
        res.add(root);
        for (int i = 0; i < to_delete.length; i++) {
            TreeNode[] cur = new TreeNode[2];
            for (int j = 0; j < res.size(); j++) {
                cur = helper(res.get(j), to_delete[i]);
                if (cur[1] != null) {
                    if (cur[0] == null) {
                        res.remove(cur[1]);
                        if (cur[1].left != null) res.add(cur[1].left);
                        if (cur[1].right != null) res.add(cur[1].right);
                    } else {
                        if (cur[0].left != null && cur[0].left.val == cur[1].val) {
                            cur[0].left = null;
                        } else {
                            cur[0].right = null;
                        }
                        if (cur[1].left != null) res.add(cur[1].left);
                        if (cur[1].right != null) res.add(cur[1].right);
                    }
                }
            }
        }
        return res;
    }
    public TreeNode[] helper(TreeNode root, int num) {
        TreeNode[] res = new TreeNode[2];
        if (root.val == num) {
            res[1] = root;
            return res;
        } else if (root.left != null && root.left.val == num) {
            res[0] = root;
            res[1] = root.left;
        } else if (root.right != null && root.right.val == num) {
            res[0] = root;
            res[1] = root.right;
        } else {
            if (root.left != null) res = helper(root.left, num);
            if (res[1] != null) return res;
            if (root.right != null) res = helper(root.right, num);
        }
        return res;
    }
}

좋은 웹페이지 즐겨찾기