LeetCode 1660. 糾正二叉樹(BFS)

Michael阿明 2021-08-15 22:28:27 阅读数:998

本文一共[544]字,预计阅读时长:1分钟~
leetcode 二叉 bfs

文章目錄

1. 題目

你有一棵二叉樹,這棵二叉樹有個小問題,其中有且只有一個無效節點,它的右子節點錯誤地指向了與其在同一層且在其右側的一個其他節點。

給定一棵這樣的問題二叉樹的根節點 root ,將該無效節點及其所有子節點移除(除被錯誤指向的節點外),然後返回新二叉樹的根結點。

自定義測試用例:

測試用例的輸入由三行組成:

TreeNode root
int fromNode (在 correctBinaryTree 中不可見)
int toNode (在 correctBinaryTree 中不可見)

當以 root 為根的二叉樹被解析後,值為 fromNode 的節點 TreeNode 將其右子節點指向值為 toNode 的節點 TreeNode 。
然後, root 傳入 correctBinaryTree 的參數中。

示例 1:
在這裏插入圖片描述

輸入: root = [1,2,3], fromNode = 2, toNode = 3
輸出: [1,null,3]
解釋: 值為 2 的節點是無效的,所以移除之。

示例 2:
在這裏插入圖片描述

輸入: root = [8,3,1,7,null,9,4,2,null,null,null,5,6], fromNode = 7, toNode = 4
輸出: [8,3,1,null,null,9,4,null,null,5,6]
解釋: 值為 7 的節點是無效的,所以移除這個節點及其子節點 2。
提示:
樹中節點個數的範圍是 [3, 10^4]-10^9 <= Node.val <= 10^9
所有的 Node.val 都是互不相同的。
fromNode != toNode
fromNode 和 toNode 將出現在樹中的同一層。
toNode 在 fromNode 的右側。
fromNode.right 在測試用例的樹中建立後為 null 。

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/correct-a-binary-tree
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。

2. 解題

  • 廣度優先搜索,按層遍曆
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {

public:
TreeNode* correctBinaryTree(TreeNode* root) {

unordered_set<TreeNode*> vis;
queue<tuple<TreeNode*,TreeNode*,int>> q; // 當前節點,其父節點,左0還是右1
q.push({
root, NULL, 0});
TreeNode* cur, *parent;
int dir;
bool finish = false;
while(!q.empty())
{

int size = q.size();
while(size--)
{

tie(cur, parent, dir) = q.front();
q.pop();
if(cur->left)
{

q.push({
cur->left, cur, 0});
vis.insert(cur->left);
}
if(cur->right)
{

if(vis.count(cur->right)) // 遇到已經訪問過的右節點,cur就是要找的節點
{

if(dir==0)
parent->left = NULL;//斷開
else
parent->right = NULL;
finish = true;
break;
}
q.push({
cur->right, cur, 1});
vis.insert(cur->right);
}
}
if(finish) break;
}
return root;
}
};

116 ms 65.7 MB C++


我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號(Michael阿明),一起加油、一起學習進步!
Michael阿明

版权声明:本文为[Michael阿明]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815222753155i.html