content: package codingquestions.leetcode;
  
  /**
   * 2641. Cousins in Binary Tree II
   * Solved
   * Medium
   * Topics
   * Companies
   * Hint
   * Given the root of a binary tree, replace the value of each node in the tree with the sum of all its cousins' values.
   * <p>
   * Two nodes of a binary tree are cousins if they have the same depth with different parents.
   * <p>
   * Return the root of the modified tree.
   * <p>
   * Note that the depth of a node is the number of edges in the path from the root node to it.
   **/
  
  import codingquestions.leetcode.ds.TreeNode;
  
  /**
   * 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;
   * }
   * }
   */
  public class CousinsinBinaryTreeII {
      public TreeNode replaceValueInTree(TreeNode root) {
          dfs(new TreeNode[]{root});
          root.val = 0;
          return root;
      }
  
      private void dfs(TreeNode[] arr) {
          if (arr.length == 0) return;
  
          int sum = 0;
          for (TreeNode node : arr) {
              if (node == null) continue;
              if (node.left != null) sum += node.left.val;
              if (node.right != null) sum += node.right.val;
          }
  
          TreeNode[] childArr = new TreeNode[arr.length * 2];
          int index = 0;
  
          for (TreeNode node : arr) {
              int curSum = 0;
              if (node.left != null) curSum += node.left.val;
              if (node.right != null) curSum += node.right.val;
  
              if (node.left != null) {
                  node.left.val = sum - curSum;
                  childArr[index++] = node.left;
              }
              if (node.right != null) {
                  node.right.val = sum - curSum;
                  childArr[index++] = node.right;
              }
          }
  
          dfs(java.util.Arrays.copyOf(childArr, index));
      }
  }
  