https://leetcode.com/problems/maximum-width-of-binary-tree/

1. Use DFS(runtime error):

  • This “runtime error” even happens on the most voted posted answer, so this solution is still usable ```cpp /**

    • Definition for a binary tree node.
    • struct TreeNode {
    • int val;
    • TreeNode *left;
    • TreeNode *right;
    • TreeNode() : val(0), left(nullptr), right(nullptr) {}
    • TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    • TreeNode(int x, TreeNode left, TreeNode right) : val(x), left(left), right(right) {}

    • }; / class Solution { public: int widthOfBinaryTree(TreeNode root) {

      1. vector<int> lefts; //left most nodes at each level
      2. int max_width = 0;
      4. dfs(root, 1, 0, lefts, max_width);
      6. return max_width;

      }

private: void dfs(TreeNode* root, int id, int depth, vector& lefts, int& max_width){ if(!root) return;

    if(depth >= lefts.size())
        lefts.push_back(id);

    max_width = max(max_width, id - lefts[depth] + 1);

    dfs(root->left, id * 2, depth + 1, lefts, max_width);
    dfs(root->right, id * 2 + 1, depth + 1, lefts, max_width);
}

}; ```

  • Idea:
    • if sign the id of the root node in a tree as 1
      • left child is id*2
      • right child is id*2 + 1
    • “width” of a tree is:
      • in the same layer(depth)
      • the rightmost node id - the leftmost node id + 1
    • so “lefts” vector above stores

id: 0 1 2 3
value: [1, 2, 4, 8]
at last

  • and we just need to keep updating max_width by “right id - left id” logic