LeetCode每日一题【c++版】

一、题目概述

        给你一个整数n表示一棵满二叉树里面节点的数目，节点编号从1到n。根节点编号为1，树中每个非叶子节点i都有两个孩子，分别是左孩子2*i和右孩子2*i+1。树中每个节点都有一个值，用下标从0开始、长度为n的整数数组cost表示，其中cost[i]是第i+1个节点的值。每次操作，你可以将树中任意节点的值增加1。你可以执行操作任意次。你的目标是让根到每一个叶子结点的路径值相等。请你返回最少需要执行增加操作多少次。

• 满二叉树：指的是一棵树，它满足树中除了叶子节点外每个节点都恰好有 2 个子节点，且所有叶子节点距离根节点距离相同。

          路径值：指的是路径上所有节点的值之和。

  输入输出示例：

          输入：n = 7, cost = [1,5,2,2,3,3,1]

          输出：6

          输入：n = 3, cost = [5,3,3]

          输出：0

  链接：2673. 使二叉树所有路径值相等的最小代价

   二、思路

          我们首先来看，对于任一叶子结点，它的值为x，它的兄弟结点的值为y。对于树上其他的结点，它们要么同时是这两个叶节点的祖先，要么同时不是这两个叶节点的祖先。对这些节点进行一次操作，要么同时增加了根到这两个叶节点的路径值 1，要么没有任何效果。因此，要想使得根到这两个叶节点的路径值相等，我们只能增加 x和 y本身。

          因此如果二者的路径值不相等，就一定是这两个叶子节点的值不等导致的，由于我们只能增加值，且每次+1，所有我们应该让较小的叶子节点值变成较大的叶子节点值，增加的操作数就是二者之差，也就是进行|x-y|次操作。

          如下图所示，叶子节点4和5到根节点的路径，除了两者之外，其余节点都相等，所以为了使得两者路径值相同，可以将节点4的值变成3即可。

          经过一次处理后，每两个叶子节点一组，它们之间到根节点的路径值就相同了。所以我们只需要再看他们的父节点即可，也就是这些父节点的的父节点为根节点的子树要实现同样的条件。如下图，可以把节点2和节点3这一层看成新的叶子节点，值为对应的路径值，所以这一层操作就是将节点3的路径值5变成节点2的路径值8，操作了三次。

          所以自底向上进行处理，先使得叶子节点到最近的根节点的子树的路径值相同，再一层一层往上，扩充子树，使得更多叶子节点到更顶层的根节点的路径值相同，直到到达根节点。因此，在整个自底向上的过程中，只要统计每个非叶子节点的两个子节点当前路径值之差，即可以得到最终的结果。由于树由数组形式给出，叶子节点在末尾出现，所以我们对数组进行逆序遍历；又因为是满二叉树，所以连续两个节点肯定是兄弟节点，所以我们每次遍历步长为2；对于满二叉树，父节点和左右孩子节点的关系为：.当i/2取取整>=1时,i/2取整单元是其父结点。

  三、复杂度分析

  时间复杂度：O(n)

  空间复杂度：O(1)

  四、代码

  #include #include using namespace std;
  class Solution
  {
  public:
      int minIncrements(int n, vector &cost)
      {
          int ans = 0;
          for (int i = n - 2; i > 0; i -= 2)
          {
              ans += abs(cost[i] - cost[i + 1]);
              cost[i / 2] += max(cost[i], cost[i + 1]);
          }
          return ans;
      }
  };
  int main()
  {
      int n = 7;
      vector cost = {1, 5, 2, 2, 3, 3, 1};
      int ans = Solution().minIncrements(n, cost);
      cout << ans << endl;
      n = 3;
      cost = {5, 3, 3};
      ans = Solution().minIncrements(n, cost);
      cout << ans << endl;
  }

           OK，问题解决，求点赞关注！如果有其他思路，或者其他语言的解题方式，欢迎大家在下面热烈讨论~