剑指offer（22）——C++实现从上到下打印二叉树

骑猪看日落 2024-04-17 06:23 37阅读 0赞

# 题目 #

从上往下打印出二叉树的每个节点，同层节点从左至右打印。即按层遍历

# 考察点 #

*  二叉树遍历方式中的按层遍历 [二叉树前中后三种遍历方式][Link 1]

# 解题思路 #

**使用队列** 使用队列存储一个节点的左右子节点，按照先进先出的思想，先出左再出右，当左出的时候，存储其左右子节点，右出的时候同理。

# 完整代码 #

/*22-从上到下打印二叉树*/
    #include<iostream>
    #include<vector>
    #include<queue>
    using namespace std;
    
    struct TreeNode {
        
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {
        
    	}
    };
    class Solution {
        
    public:
    	vector<int> PrintFromTopToBottom(TreeNode* root) {
        
    		vector<int> result;
    		if (root == NULL) return result;
    		queue<TreeNode*> q;
    		q.push(root);
    		while (!q.empty())
    		{
        
    			result.push_back(q.front()->val);//将队列的第一个元素保存进result
    
    			if (q.front()->left != NULL)//压入左节点
    				q.push(q.front()->left);
    			if (q.front()->right != NULL)
    				q.push(q.front()->right);//压入右节点
    
    			q.pop();//弹出第一个元素
    		}
    		return result;
    	}
    };
    int main()
    {
        
    	TreeNode *root = new TreeNode(1); TreeNode *p1 = new TreeNode(2); TreeNode *p2 = new TreeNode(3);
    	TreeNode *p3 = new TreeNode(4); TreeNode *p4 = new TreeNode(5); TreeNode *p5 = new TreeNode(6); TreeNode *p6 = new TreeNode(7);
    	root->left = p1; root->right = p2; p1->left = p3; p1->right = p4; p2->left = p5; p2->right = p6;
    	Solution s;
    	vector<int> result;
    	result = s.PrintFromTopToBottom(root);
    	for (int i = 0; i < result.size(); i++)
    	{
        
    		cout << result[i];
    	}
    	cout << endl;
    	return 0;
    }

[Link 1]: https://blog.csdn.net/fengwenpei/article/details/96462281