LeetCode 662 Maximum Width of Binary Tree
程序员文章站
2022-03-31 12:24:57
...
LeetCode 662
Maximum Width of Binary Tree
-
Problem Description:
比较二叉树每一层宽度,输出最大宽度。这里对宽度的定义是最左非空结点与最右非空结点之间的结点数,包括边界。
具体的题目信息:
https://leetcode.com/problems/maximum-width-of-binary-tree/description/ - Example:
- Solution:
- 解题思路:
刚开始层次遍历+单向队列一直超时,在讨论区看到大神用双向队列解答的,学习借鉴一波:) - 编程实现:
- 解题思路:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if (root == NULL) return 0;
int maxlen = 0;
deque<TreeNode*> node;
node.push_back(root);
while(!node.empty()) {
int len = node.size();
maxlen = len>maxlen?len:maxlen;
for (int i = 0; i < len; i++) {
TreeNode* p = node.front();
node.pop_front();
if (p) {
node.push_back(p->left);
node.push_back(p->right);
} else {
node.push_back(NULL);
node.push_back(NULL);
}
}
//通过pop出NULL结点得到右侧第一个非空结点
while(!node.empty()) {
if(node.back() == NULL)
node.pop_back();
else
break;
}
//通过pop出NULL结点得到左侧第一个非空结点
while(!node.empty()) {
if (node.front() == NULL)
node.pop_front();
else
break;
}
}
return maxlen;
}
};
推荐阅读
-
leetcode笔记:Invert Binary Tree
-
【leetcode】-700. Search in a Binary Search Tree 查找二叉搜索树
-
Leetcode——108. Convert Sorted Array to Binary Search Tree
-
Leetcode 108. Convert Sorted Array to Binary Search Tree
-
21天刷题计划之17.1—maximum-depth-of-binary-tree(二叉树的最大深度)(Java语言描述)
-
LeetCode 236 -- 二叉树的最近公共祖先 ( Lowest Common Ancestor of a Binary Tree ) ( C语言版 )
-
LeetCode 235--二叉搜索树的最近公共祖先 ( Lowest Common Ancestor of a Binary Search Tree ) ( C语言版 )
-
LeetCode 235. Lowest Common Ancestor of a Binary Search Tree 二叉搜索树
-
[Leetcode] 235. Lowest Common Ancestor of a Binary Search Tree
-
leetcode 235. Lowest Common Ancestor of a Binary Search Tree(二叉树的最低共同祖先)