剑指 Offer 32 - I. 从上到下打印二叉树 - 力扣（LeetCode）

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

例如:
给定二叉树: [3,9,20,null,null,15,7],

3

/
9 20
/
15 7
返回：

[3,9,20,15,7]

思路：

  1. 按层打印明显为bfs

复杂度：

O(n)

题解：

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
      queue<TreeNode*> q;
      vector<int> res;
      if(root!=nullptr)//首项特判
        q.push(root);
      while(!q.empty()){
          int size=q.size();//每层数量
          for(int i=0;i<size;i++){
              TreeNode* node=q.front();
              q.pop();
              res.push_back(node->val);
              if(node->left!=nullptr)
                q.push(node->left);
              if(node->right!=nullptr)
                q.push(node->right);
          }
      }
      return res;
    }
};
  1. z字形
class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int x = 0, y = n - 1;
        while (x < m && y >= 0) {
            if (matrix[x][y] == target) {
                return true;
            }
            if (matrix[x][y] > target) {
                --y;
            }
            else {
                ++x;
            }
        }
        return false;
    }
};