2024.2.7力扣每日一题——二叉树的堂兄弟节点2

2024.2.7

• • • 题目来源
    • 我的题解
    • • 方法一 哈希表+层序遍历（自己的想法，硬在每一层去算）
      • 方法二 广度优先遍历（官方题解，在上一层求下一层）

题目来源

力扣每日一题；题序：2461

我的题解

方法一 哈希表+层序遍历（自己的想法，硬在每一层去算）

使用两个哈希表分别映射parent <子节点，父节点>，children<父节点，子节点列表>。children需要首先将将根节点加入，然后使用层序遍历的方式遍历遍历每一层，并在遍历过程中记录该层所有节点的和sum，以及parent和children，然后使用一个列表存储一层的所有节点（因为层序遍历过后就不知道那些节点是该层的了），然后根据parent找到节点的父节点，再根据children找到自己父节点下的所有子节点，再计算自己父节点下的所有节点的和sub，然后将自己的值改变为sum-sub（这里需要使用数组暂存，否则计算该层后面的节点时会出现问题）。

时间复杂度：应该是O( n 2 n^2 n2)。
空间复杂度：O(n)

public TreeNode replaceValueInTree(TreeNode root) {
    Map<TreeNode,List<TreeNode>> children=new HashMap<>();
    Map<TreeNode,TreeNode> parent=new HashMap<>();
    Queue<TreeNode> queue=new LinkedList<>();
    queue.offer(root);
    List<TreeNode> l=new LinkedList<>();
    l.add(root);
    children.put(null,l);
    while(!queue.isEmpty()){
        int sz=queue.size();
        List<TreeNode> list=new LinkedList<>(queue);
        //计算当前层所有节点的和
        int sum=0;
        for(int i=0;i<sz;i++){
            TreeNode t=queue.poll();
            sum+=t.val;
            l=new LinkedList<>();
            if(t.left!=null){
                queue.offer(t.left);
                parent.put(t.left,t);
                l.add(t.left);
            }
            if(t.right!=null){
                queue.offer(t.right);
                parent.put(t.right,t);
                l.add(t.right);
            }
            children.put(t,l);
        }
        //暂存需要改变的值
        int[] v=new int[sz];
        int i=0;
        for(TreeNode t:list){
        	//查找当前节点的父节点下的所有节点
            l=children.get(parent.get(t));
            int sub=0;
            for(TreeNode tt:l){
                sub+=tt.val;
            }
            v[i++]=sum-sub;
        }
        i=0;
        for(TreeNode t:list){
            t.val=v[i++];
        }
    }
    return root;
}

方法二 广度优先遍历（官方题解，在上一层求下一层）

在广度优先搜索的过程中，通过第 n−1层去遍历第 n层的节点时，可以顺便统计第 n 层节点的和 sum。由于更新 x 的值时需要知道 y 的值（有可能不存在），因此需要通过 n−1 层对第 n 层进行第二次遍历，这时就可以使用 sum−x−y 更新 x 的值了。

时间复杂度：O(n)。
空间复杂度：O(n)

 public TreeNode replaceValueInTree(TreeNode root) {
    // 根节点必然为0
    root.val=0;
    Queue<TreeNode> queue=new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        int sz=queue.size();
        int sum=0;
        //计算下一层的所有节点之和
        for(TreeNode t:queue){
            if(t.left!=null)
                sum+=t.left.val;
            if(t.right!=null)
                sum+=t.right.val;
        }
        for(int i=0;i<sz;i++){
            TreeNode t=queue.poll();
            //非堂兄弟的兄弟节点的和
            int sub=(t.left!=null?t.left.val:0)+(t.right!=null?t.right.val:0);
            // 左子节点
            if(t.left!=null){
                t.left.val=sum-sub;
                queue.offer(t.left);
            }
            // 右子节点
            if(t.right!=null){
                t.right.val=sum-sub;
                queue.offer(t.right);
            }
        }
    }
    return root;
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈