[剑指offer]刷题笔记

• 按之字顺序打印二叉树

• 把二叉树打印成多行

按之字顺序打印二叉树【树】【常考！！！】

题目描述：请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

我的想法：类似于二叉树的层次遍历，是奇数行的用队列从左向右遍历，偶数行的逆序。

class Solution {
public:
  //奇数行从左往右打印 偶数行从右往左打印
  vector<vector<int> > Print(TreeNode* pRoot) {
      vector<vector<int>> res;
      if(pRoot==NULL)
          return res;
      TreeNode* p=pRoot;
      queue<TreeNode*> que;  //定义一个队列用来从左向右输出的
      bool even=false;  //判断是不是偶数 一开始是1是奇数
      que.push(p);
      while(!que.empty())
      {
          vector<int> vec;    //这个是局部变量否则每次都会把前边的在输出一遍
          int size=que.size();
          for(int i=0;i<size;i++)
          {
              //类似于二叉树的层次遍历
              TreeNode* head=que.front();
              que.pop();
              vec.push_back(head->val);
              if(head->left!=NULL)
                  que.push(head->left);
              if(head->right!=NULL)
                  que.push(head->right);
          }
          if(even)  //是偶数的时候要反转
          {
              reverse(vec.begin(), vec.end());
          }
          res.push_back(vec);
          even=!even;
      }
      return res;
  }
};

栈的方法

public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        int layer = 1;
        //s1存奇数层节点
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        s1.push(pRoot);
        //s2存偶数层节点
        Stack<TreeNode> s2 = new Stack<TreeNode>();
         
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
         
        while (!s1.empty() || !s2.empty()) {
            if (layer%2 != 0) {
                ArrayList<Integer> temp = new ArrayList<Integer>();
                while (!s1.empty()) {
                    TreeNode node = s1.pop();
                    if(node != null) {
                        temp.add(node.val);
                        System.out.print(node.val + " ");
                        s2.push(node.left);
                        s2.push(node.right);
                    }
                }
                if (!temp.isEmpty()) {
                    list.add(temp);
                    layer++;
                    System.out.println();
                }
            } else {
                ArrayList<Integer> temp = new ArrayList<Integer>();
                while (!s2.empty()) {
                    TreeNode node = s2.pop();
                    if(node != null) {
                        temp.add(node.val);
                        System.out.print(node.val + " ");
                        s1.push(node.right);
                        s1.push(node.left);
                    }
                }
                if (!temp.isEmpty()) {
                    list.add(temp);
                    layer++;
                    System.out.println();
                }
            }
        }
        return list;
    }

上道题变形：把二叉树打印成多行

题目描述：从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

class Solution {
public:
      vector<vector<int> > Print(TreeNode* pRoot) {
          vector<vector<int>> res;
          if(pRoot==NULL)
              return res;
          queue<TreeNode *> que;
          TreeNode* p=pRoot;
          que.push(p);
          while(!que.empty())
          {
              int size=que.size();   //每次都是一个新的队列
              vector<int> vec;  //每次都是一个新的数组
              for(int i=0;i<size;i++)
              {
                  TreeNode* head=que.front();
                  vec.push_back(head->val);
                  que.pop();
                  if(head->left!=NULL)
                      que.push(head->left);
                  if(head->right!=NULL)
                      que.push(head->right);
                  
              }
              res.push_back(vec);
          }
          return res;
      }
  
};