二叉树的层次遍历

102.二叉树的层次遍历
给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。
在这里插入图片描述
来源：力扣（LeetCode）
链接：link
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析：本题使用宽度优先搜索（BFS），对每一层的元素同时进入队列，然后出队时同时出队，再换下一层的同时入队。

C++源码：

/** 
* 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:    
	vector<vector<int>> levelOrder(TreeNode* root) 
	{        
		vector<vector<int>> ans;        
		if(root == NULL)            
			return ans;        
		queue<TreeNode*> q;        
		TreeNode* p = root;        
		q.push(root);        
		while(!q.empty())        
		{            
			vector<int> step;            
			int width = q.size();            
			for(int i = 0;i < width;i++)//这一层循环用来将之前层的元素出队，将下一层元素入队            
			{                
				p = q.front();                
				step.push_back(p->val);                
				q.pop();                
				if(p->left) q.push(p->left);                
				if(p->right) q.push(p->right);            
			}            
			ans.push_back(step);        
		}        
		return ans;    
	}
};

本文链接：https://blog.csdn.net/qq_43655213/article/details/104588451

智能推荐

二叉树的层次遍历

二叉树的层次遍历题目描述 : 给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。例如: 给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ &n...

102.二叉树的层次遍历

难度：中等题目描述：思路总结：看到这题，不知是受到什么毒害，首先想到了队列和栈，但发现得用两个分别存当前和子节点，遂放弃，看官方题解，还是两种方法，递归和迭代。题解一：（递归）题解一结果：题解二：（迭代）题解二结果：...

107.二叉树的层次遍历Ⅱ

难度：简单题目描述： **思路总结：**首先很直观的想到了，层次遍历，将结果逆序返回。题解一：（递归）题解一结果：题解二：（迭代）题解二结果：后记：其实这两题的这两种做法，相对于层次遍历来说也就是，一个逆序操作，只是将逆序操作放到递归和遍历中了，使用的是Python中list的insert方法。...

102_二叉树的层次遍历

...

二叉树的层次遍历

题目思路二叉树的层次遍历有两种方法，分别是迭代法和递归法迭代法迭代法主要用到队列，将下一层的元素放到队列尾部，从队列首部弹出元素，代码如下递归法先用递归求出二叉树的高度然后再递归的写进容器...

二叉树的层次遍历

智能推荐

猜你喜欢