Leetcode#662. Maximum Width of Binary Tree

本文主要是介绍Leetcode#662. Maximum Width of Binary Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：求二叉树的最大宽度

class Solution {
public:void DFS(TreeNode* root, int depth, int index, vector<int> &start, int &maxWidth){if(root == NULL)return;else{if(depth >= start.size())start.push_back(index);maxWidth = max(maxWidth, index - start[depth] + 1);DFS(root->left, depth + 1, 2 * index, start, maxWidth);DFS(root->right, depth + 1, 2 * index + 1, start, maxWidth);}}int widthOfBinaryTree(TreeNode* root) {int maxWidth = 0;vector<int> start;DFS(root, 0 , 1, start, maxWidth);return maxWidth;}
};

20180816更新，非递归实现

class Solution{
public:int widthOfBinaryTree(TreeNode *root){if(root == NULL){ return 0; }if(root->left == NULL && root->right == NULL){ return 1; }int max_width = 1;deque<pair<TreeNode*,int>> q;q.push_back({root, 1});while(!q.empty()){int sz = q.size();for(int i = 1; i<=sz; ++i){auto pair = q.front();q.pop_front();if(pair.first->left){q.push_back({pair.first->left, pair.second*2});}if(pair.first->right){q.push_back({pair.first->right,pair.second*2+1});}}if(q.size() > 1){max_width = max(max_width,q.back().second - q.front().second+1);}}return max_width;}
};

这篇关于Leetcode#662. Maximum Width of Binary Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---