分层次遍历二叉树

编程软件eclipse

jdk1.8

1.递归的方法　　二叉树本身就带有递归属性，通常我们可以用递归方法解决。假设要访问第k层节点，那么其实可以转皇城分别访问“以该二叉树根节点的左右子节点为根节点的两棵子树”中层次为k-1的节点。此方法需要求出二叉树的深度，其实可以直接访问到二叉树某一层次失败的时候返回就可以了。　　这个方法的问题是递归调用，效率较低。而且对每一层的访问都需要从根节点开始，效率极差。　　最坏的情况下（不平衡树）时间复杂度为O(n^2),空间复杂度O(1)[java] view plain copy 在CODE上查看代码片派生到我的代码片//输出以root为根节点中的第level层中的所有节点（从左至右），成功返回1  //失败返回0  //root为二叉树根节点  //level为层次数，其中根节点为第0层  int PrintNodeAtLevel(TreeNode *root, int level) {      if (!root || level < 0) return 0;      if (level == 0){          cout<val;          return 1;      }        return PrintNodeAtLevel(root->left, level - 1) + PrintNodeAtLevel(root->right, level - 1);  }    //层次遍历二叉树  //root，二叉树的根节点  void LevelOrder(TreeNode *root) {      for (int level = 0; ; level++) {          if (!PrintNodeAtLevel(root, level))               break;          cout<

2. 使用数组和两个游标的方法　　在访问k层的时候，我们只需要知道k-1层的信息就足够了，所以在访问第k层的时候，要是能够知道k-1层的节点信息，就不再需要从根节点开始遍历了。　　根据上述分析，可以从根节点出发，依次将每一层的根节点从左往右压入一个数组，并并用一个游标cur记录当前访问的节点，另一个游标last指示当前层次的最后一个节点的下一个位置，以cur===last作为当前层次访问结束的条件，在访问某一层的同时将该层的所有节点的子节点压入数组，在访问完某一层之后，检查是否还有新的层次可以访问，直到检查完所有的层次（不再有新的节点可以访问）　　这种方法需要一个vector一直存储所有节点，空间效率较差。　　时间复杂度为O(n),空间复杂度为O(n)[java] view plain copy 在CODE上查看代码片派生到我的代码片void LevelOrder(TreeNode *root) {      if (root == NULL) return;      vector vec; //这里使用stl中的vector代替数组，可利用到                              //其动态扩展的属性      vec.push_back(root);      int cur = 0, last = vec.size();      while (cur < vec.size()) {          last = vec.size();            while (cur < last) {              cout<val;              if (vec[cur]->left)                   vec.push_back(vec[cur]->left);              if(vec[cur]->right)                  vec.push_back(vec[cur]->right);              ++cur;          }          cout< que = new LinkedList();      while(root!=null)      {          System.out.print(p.data);          if(p.left!=null)              que.add(p.left);          if(p.right!=null)              que.add(p.right);          p=que.poll();      }  }