LeetCode 1660. 纠正二叉树（BFS）

Michael阿明

发布于 2021-09-06 11:37:01

3400

发布于 2021-09-06 11:37:01

文章被收录于专栏：Michael阿明学习之路

文章目录

- 1. 题目
- 2. 解题

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阿明），一起加油、一起学习进步！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/08/15 ，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树