[leetCode 丶每日随机] 2641. 二叉树的堂兄弟节点 II

原题: 2641. 二叉树的堂兄弟节点II

描述:

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

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

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

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

示例 1：

示例1

输入： 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:

示例2

输入： root = [3,1,2]
输出： [0,0,0]
解释： 上图展示了初始的二叉树和修改每个节点的值之后的二叉树。

值为 3 的节点没有堂兄弟，所以值修改为 0 。

值为 1 的节点没有堂兄弟，所以值修改为 0 。

值为 2 的节点没有堂兄弟，所以值修改为 0 。

提示

树中节点数目的范围是 [1, 10^5] 。
1 <= Node.val <= 10^4

个人版答案

执行用时: 54ms 执行内存消耗: 88.06M

/**
 * 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 replaceValueInTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        Map<Integer/* index */, Integer/* sum */> map = new HashMap<>();
        preCount(root, 0, map);
        change(root, 0, map);
        return root;
    }

    private void preCount(TreeNode tn, int index, Map<Integer/* index */, Integer/* sum */> map) {
        if (tn != null) {
            int sum = map.getOrDefault(index, 0);
            map.put(index, sum + tn.val);
            index++;
            if (Objects.nonNull(tn.left)) {
                preCount(tn.left, index, map);
            }
            if (Objects.nonNull(tn.right)) {
                preCount(tn.right, index, map);
            }
        }
        return;
    }

    private void change(TreeNode tn, int index, Map<Integer/* index */, Integer/* sum */> map) {
        if (tn != null) {
            if (index == 0) {
                tn.val = 0;
                index++;
                if (Objects.nonNull(tn.left)) {
                    tn.left.val = 0;
                    change(tn.left, index, map);
                }
                if (Objects.nonNull(tn.right)) {
                    tn.right.val = 0;
                    change(tn.right, index, map);
                }
            } else {
                if (Objects.nonNull(map.get(index + 1))) {
                    int sum = map.get(index + 1);
                    index++;
                    if (Objects.nonNull(tn.left)) {
                        sum -= tn.left.val;
                    }
                    if (Objects.nonNull(tn.right)) {
                        sum -= tn.right.val;
                    }
                    if (Objects.nonNull(tn.left)) {
                        tn.left.val = sum;
                        change(tn.left, index, map);
                    }
                    if (Objects.nonNull(tn.right)) {
                        tn.right.val = sum;
                        change(tn.right, index, map);
                    }
                }
            }
        }
    }
}

11ms 答案及进阶版**

/**
 * 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 replaceValueInTree(TreeNode root) {
        Queue<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        int presum = 0;
        root.val = 0;
        while (q.size()!=0) {
            int cursum = 0;
            for(int i= q.size();i>0;i--){
                TreeNode n = q.poll();
                n.val+=presum;
                if(n.left!=null && n.right!=null){
                    cursum+=n.left.val+n.right.val;
                    n.left.val = -n.left.val-n.right.val;
                    n.right.val = n.left.val;
                    q.add(n.left);
                    q.add(n.right);
                }else if(n.left!=null){
                    cursum+=n.left.val;
                    n.left.val = -n.left.val;
                    q.add(n.left);
                }else if(n.right!=null){
                    cursum+=n.right.val;
                    n.right.val = -n.right.val;
                    q.add(n.right);
                }
            }
            presum = cursum;
        }
        return root;
    }
}