二叉树的宽度

算法思想：用一个w维护当前二叉树的宽度，使用层序遍历的方式，每次入队后更新w的值。

代码语言：javascript复制

#include <bit/stdc  .h>
using namespace std;

struct TreeNode {
	int val;
	TreeNode *left, *right;
};

int width(TreeNode *root) {
	if (!root) return 0;
	queue<TreeNode*> q;
	q.push(root);
	int w = 1;// 当前二叉树的宽度为1
	while (!q.empty()) {
		int size = q.size();
		while (size > 0) {
			auto f = q.front();q.pop();
			size --;
			if (f->left) q.push(f->left);
			if (f->right) q.push(f->right);
		}
		w = max(w, (int)q.size());
	}
	return w;
}

二叉树 遍历 算法

0 人点赞