剑指offer | 32 - I. 从上到下打印二叉树

傷城~ 2022-12-28 01:41 190阅读 0赞

题目：

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例如:

  1. 给定二叉树: [3,9,20,null,null,15,7],
  3.     3
  4.    / \
  5.   9  20
  6.     /  \
  7.    15   7
  9. 返回：
  11. [3,9,20,15,7]

提示：

  1. 节点总数 <= 1000

思路： 借助queue进行层次遍历。

  1. /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
  2. class Solution { 
  3. public:
  4.     vector<int> levelOrder(TreeNode* root) { 
  5.         if(!root) return { };
  6.         vector<int> res;
  7.         queue<TreeNode *> bfs; // 广度优先搜索（层次遍历）
  8.         bfs.push(root);
  9.         while(!bfs.empty())
  10.         { 
  11.             TreeNode *temp = bfs.front();
  12.             res.push_back(bfs.front() -> val);
  13.             bfs.pop();
  14.             if(temp -> left) bfs.push(temp -> left);
  15.             if(temp -> right) bfs.push(temp -> right);
  16.         }
  17.         return res;
  18.     }
  19. };

发表评论

表情：
评论列表 （有 0 条评论，190人围观）

还没有评论，来说两句吧...

相关阅读