LeetCode 2641. 二叉树的堂兄弟节点 II:层序遍历并记下兄弟节点

这篇具有很好参考价值的文章主要介绍了LeetCode 2641. 二叉树的堂兄弟节点 II:层序遍历并记下兄弟节点。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【LetMeFly】2641.二叉树的堂兄弟节点 II:层序遍历并记下兄弟节点

力扣题目链接:https://leetcode.cn/problems/cousins-in-binary-tree-ii/

给你一棵二叉树的根 root ,请你将每个节点的值替换成该节点的所有 堂兄弟节点值的和 

如果两个节点在树中有相同的深度且它们的父节点不同,那么它们互为 堂兄弟 。

请你返回修改值之后,树的根 root 

注意,一个节点的深度指的是从树根节点到这个节点经过的边数。

 

示例 1:

LeetCode 2641. 二叉树的堂兄弟节点 II:层序遍历并记下兄弟节点,题解,# 力扣LeetCode,leetcode,题解,二叉树,层序遍历,哈希表

输入:root = [5,4,9,1,10,null,7]
输出:[0,0,0,7,7,null,11]
解释:上图展示了初始的二叉树和修改每个节点的值之后的二叉树。
- 值为 5 的节点没有堂兄弟,所以值修改为 0 。
- 值为 4 的节点没有堂兄弟,所以值修改为 0 。
- 值为 9 的节点没有堂兄弟,所以值修改为 0 。
- 值为 1 的节点有一个堂兄弟,值为 7 ,所以值修改为 7 。
- 值为 10 的节点有一个堂兄弟,值为 7 ,所以值修改为 7 。
- 值为 7 的节点有两个堂兄弟,值分别为 1 和 10 ,所以值修改为 11 。

示例 2:

LeetCode 2641. 二叉树的堂兄弟节点 II:层序遍历并记下兄弟节点,题解,# 力扣LeetCode,leetcode,题解,二叉树,层序遍历,哈希表

输入:root = [3,1,2]
输出:[0,0,0]
解释:上图展示了初始的二叉树和修改每个节点的值之后的二叉树。
- 值为 3 的节点没有堂兄弟,所以值修改为 0 。
- 值为 1 的节点没有堂兄弟,所以值修改为 0 。
- 值为 2 的节点没有堂兄弟,所以值修改为 0 。

 

提示:

  • 树中节点数目的范围是 [1, 105]
  • 1 <= Node.val <= 104

方法一:层序遍历并记下兄弟节点

层序遍历很简单:

使用一个队列或数组(初始将根节点放入数组),在数组非空时:

创建临时新数组并遍历数组中的所有节点,

处理当前节点,将节点的子节(如有)放入新数组中。

遍历结束时,交换临时数组和上一个数组。

我们要做的修改是:

  1. 将节点及其兄弟节点同时入队
  2. 遍历某一层时,遍历两次。第一次统计这一层的元素之和、记录每个节点的值(后续可能会变化)、子节点放入新数组(如有);第二次修改每个节点的值( 这层值的总和 − 当前节点值 − 兄弟节点值 这层值的总和 - 当前节点值 - 兄弟节点值 这层值的总和当前节点值兄弟节点值

最终返回根节点即可。

  • 时间复杂度 O ( s i z e ( t r e e ) ) O(size(tree)) O(size(tree))
  • 空间复杂度 O ( max ⁡ s i z e ( l a y e r ) ) O(\max size(layer)) O(maxsize(layer))

AC代码

C++
class Solution {
public:
    TreeNode* replaceValueInTree(TreeNode* root) {
        vector<pair<TreeNode*, TreeNode*>> v = {{root, nullptr}, };  // [<thisNode, broNode>, ...]
        while (v.size()) {
            int valSum = 0;
            vector<pair<TreeNode*, TreeNode*>> nextV;
            unordered_map<TreeNode*, int> originalVal;
            for (auto&& [thisNode, broNode] : v) {
                originalVal[thisNode] = thisNode->val;
                valSum += thisNode->val;
                if (thisNode->left) {
                    nextV.push_back({thisNode->left, thisNode->right});
                }
                if (thisNode->right) {
                    nextV.push_back({thisNode->right, thisNode->left});
                }
            }
            for (auto&& [thisNode, broNode] : v) {
                thisNode->val = valSum - thisNode->val - originalVal[broNode];
            }
            swap(v, nextV);  // 这里不可:memmove(&v, &nextV, nextV.size());
        }
        return root;
    }
};
Python
# from collections import defaultdict

# # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def replaceValueInTree(self, root: TreeNode) -> TreeNode:
        v = [(root, None)]
        while v:
            valSum = 0
            originalVal = defaultdict(int)
            nextV = []
            for thisNode, broNode in v:
                valSum += thisNode.val
                originalVal[thisNode] = thisNode.val
                if thisNode.left:
                    nextV.append((thisNode.left, thisNode.right))
                if thisNode.right:
                    nextV.append((thisNode.right, thisNode.left))
            for thisNode, broNode in v:
                thisNode.val = valSum - thisNode.val - originalVal[broNode]
            v = nextV
        return root

同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/136066230文章来源地址https://www.toymoban.com/news/detail-830655.html

到了这里,关于LeetCode 2641. 二叉树的堂兄弟节点 II:层序遍历并记下兄弟节点的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包