LeetCode 1110. Delete Nodes And Return Forest(java)
2667 단어 Tree
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;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Bottom up 주제 1 Leet Code124.Binary Tree Maximum Path Sumbottom up의 방법은 모든 node에 저장해야 할 데이터를 새로운 클래스에 기록하는 것을 말한다. dfs를 할 때 각 노드에서 본 노드의 조작을 한 다음에 새로운 클래스의 대상을 만들고 대상에 기록해야 할 데이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.