🌴 纠正二叉树
📝 题目描述
你有一棵二叉树，这棵二叉树有个小问题，其中有且只有一个无效节点，它的右子节点错误地指向了与其在同一层且在其右侧的一个其他节点。
给定一棵存在这样的问题的二叉树的根节点root，将该无效节点及其所有子节点移除（除被错误指向的节点外），然后返回该二叉树的根节点。
📋 代码模板
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 TreeNode correctBinaryTree(TreeNode root) {
}
}typescript
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function correctBinaryTree(root: TreeNode | null): TreeNode | null {
}💡 提示
- 树中节点个数的范围是
- 所有的
都是互不相同的
🚀 示例
🖊️ 题解
DFS
可惜没有如果
java
class Solution {
public TreeNode correctBinaryTree(TreeNode root) {
boolean[] flag = new boolean[]{false};
return dfs(root, new HashSet<>(), flag);
}
private TreeNode dfs(TreeNode node, Set<TreeNode> set, boolean[] flag) {
if (node == null || flag[0]) {
return node;
}
if (node.right != null && set.contains(node.right)) {
flag[0] = true;
return null;
}
set.add(node);
node.right = dfs(node.right, set, flag);
node.left = dfs(node.left, set, flag);
return node;
}
}typescript
function correctBinaryTree(root: TreeNode | null): TreeNode | null {
return dfs(root, new Set<TreeNode>(), [false]);
}
function dfs(node: TreeNode | null, set: Set<TreeNode>, flag: boolean[]): TreeNode | null {
if (node == null || flag[0]) {
return node;
}
if (node.right != null && set.has(node.right)) {
flag[0] = true;
return null;
}
set.add(node);
node.right = dfs(node.right, set, flag);
node.left = dfs(node.left, set, flag);
return node;
}BFS
食杂店
java
class Solution {
public TreeNode correctBinaryTree(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.right != null) {
if (node.right.right != null && queue.contains(node.right.right)) {
node.right = null;
return root;
}
queue.offer(node.right);
}
if (node.left != null) {
if (node.left.right != null && queue.contains(node.left.right)) {
node.left = null;
return root;
}
queue.offer(node.left);
}
}
return root;
}
}typescript
function correctBinaryTree(root: TreeNode | null): TreeNode | null {
const queue: TreeNode[] = [];
queue.push(root!);
while (queue.length > 0) {
const node: TreeNode = queue.shift()!;
if (node.right != null) {
if (node.right.right != null && queue.includes(node.right.right)) {
node.right = null;
return root;
}
queue.push(node.right);
}
if (node.left != null) {
if (node.left.right != null && queue.includes(node.left.right)) {
node.left = null;
return root;
}
queue.push(node.left);
}
}
return root;
}