2

I was doing leetcode 834. Sum of Distances in Tree, and I figure a way to solve it with two dfs. But, the first solution received tle when experienced a test set of 10000 nodes. After seeing the answer, I did some simple changes and the answer was accepted.

I don't know why these two functions perform so differently since they are all O(n).

The dfs function is aimed to calculate how many nodes are there under node 'current' and store them in an array 'child'. 'tree' is a 2D vector that contains the edges of the tree in list structure.

old function which received tle:

int dfs(vector <vector <int>> tree, int previous, int current)
    {
        int s = tree[current].size();
        int r = 0;
        for (int i = 0; i < s; ++i){
            if (tree[current][i] == previous) continue;
            r += dfs(tree, current, tree[current][i]);
        }
        child[current] = r;
        d_root += r;
        return r + 1;
    }

new function that is accepted:

void dfs(int previous, int current)
    {
        int s = tree[current].size();
        int r = 0;
        for (auto& a : tree[current]){
            if (a == previous) continue;
            dfs(current, a);
            r += child[a] + 1;
        }
        child[current] = r;
        d_root += r;
    }
Parisa.H.R
  • 3,303
  • 3
  • 19
  • 38
RafaelDD
  • 45
  • 4
  • 1
    Simply ignore the d_root, it has nothing to do with these functions – RafaelDD Apr 12 '22 at 07:35
  • 8
    Read about passing by value vs passing by reference. I would suggest investing some money and time into a good introductory C++ [book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) before solving random coding exercises on random websites. – Evg Apr 12 '22 at 07:37
  • 8
    Your first copies the entire `tree` on every recursion. – molbdnilo Apr 12 '22 at 07:37
  • @molbdnilo, got it, just add a & and it passed, thanks – RafaelDD Apr 12 '22 at 07:39
  • @Evg, I have learned these..... Somehow forgot when coding, anyway, thanks – RafaelDD Apr 12 '22 at 07:41
  • 2
    @RafaelDD `tle` -- When describing the issue, please don't use abbreviations and acronyms that other C++ programmers know nothing about. Explicitly state what "tle" means or stands for. Contrary to what you may believe, most C++ programmers do not go to those "online coding" sites and thus do not know the lingo being used there. – PaulMcKenzie Apr 12 '22 at 08:05
  • @molbdnilo not just that, it also shadows the other `tree` that must exist up some scope for the second to work. – Caleth Apr 12 '22 at 08:14

0 Answers0