C++ 4 lines O(n) runtime and O(h) space


  • 0
    V

    For each tree level, I am tracking the position of the leftmost element. As I am traversing the tree, I am calculating the width for the current element, and returning the maximum width.

    int width(TreeNode* r, int l, int pos, vector<int>& lmost) {
        if (r == nullptr) return 0;
        if (lmost.size() <= l) lmost.push_back(pos);
        return max(pos - lmost[l] + 1, max(width(r->right, l + 1, pos * 2, lmost), width(r->left, l + 1, pos * 2 - 1, lmost)));
    }
    int widthOfBinaryTree(TreeNode* root) {
        return width(root, 0, 1, vector<int>() = {});
    }
    

Log in to reply
 

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