0ms C++ Bottom Up One-Pass Solution.


  • 2
    F

    Instead of really doing finding/removing again and again, we can do it in one pass and get all results.

    One thing I want to clarify is, even if you do it in the naive way (find all leaves and then remove them and then find all leaves again and removes them), the complexity is also O(n), just with a bigger constant.

    class Solution {
        vector<vector<int>>  result;
        int solve(TreeNode * root)
        {
            if(root == nullptr)
                return -1;
            if (root->left == nullptr && root->right == nullptr)
            {
                if (result.empty())
                    result.emplace_back();
                result[0].push_back(root->val);
                return 0;
            }
            int l = solve(root->left);
            int r = solve(root->right);
            int level = max(l, r) + 1;
            if (level >= result.size())
                result.emplace_back();
            result[level].push_back(root->val);
            return level;
        }
    public:
        vector<vector<int>> findLeaves(TreeNode* root) {
            solve(root);
            return result;
        }
    };

  • 0

    The naive way is not O(n) but only O(n^2).


  • 1
    F

    Naive way is only O(n^2) in worst case where the tree degenerates to a linked list. Almost all tree-related algorithm has this same worst case O(n^2) complexity, but we still consider them O(nlogn).

    In average case, to see why naive way is O(n), first, you need to realize there are n/2 leave nodes. So each time you remove n/2 nodes from the tree, and you do it logN times, so the complexity is N + N/2 + N/4 + ... + 1 = O(2N) = O(N)


  • 0
    This post is deleted!

  • 0

    "Almost all tree-related algorithm has this same worst case O(n^2) complexity, but we still consider them O(nlogn)."

    I doubt it. Can you name some?


  • 1
    F

    Why do you use tree? Because it support some nice logN operation right? But what if each node of the tree has one single child, in this case, it becomes a linked list, and every logN operation becomes O(N) (And if you do it for N elements, it is O(NLogN) --> O(N^2). That being said, I might be wrong with the phrase "Almost-all", the correct word should be "ALL" -- all logN operations will become O(N) in this case. Can you name ANY operation that runs still in O(logN) when the tree degenerates to a linked list?

    Anyway, this is not the point, the point is the naive way's complexity is O(N) NOT O(N^2). Do you agree on this part after my explanation?


  • 0
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.