• 按之字順序打印二叉樹(shù)

• 把二叉樹(shù)打印成多行

按之字順序打印二叉樹(shù)【樹(shù)】【?？迹。?！】

題目描述：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)按照之字形打印二叉樹(shù)，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類(lèi)推。

我的想法：類(lèi)似于二叉樹(shù)的層次遍歷，是奇數(shù)行的用隊(duì)列從左向右遍歷，偶數(shù)行的逆序。

class Solution {
public:
  //奇數(shù)行從左往右打印 偶數(shù)行從右往左打印
  vector<vector<int> > Print(TreeNode* pRoot) {
      vector<vector<int>> res;
      if(pRoot==NULL)
          return res;
      TreeNode* p=pRoot;
      queue<TreeNode*> que;  //定義一個(gè)隊(duì)列用來(lái)從左向右輸出的
      bool even=false;  //判斷是不是偶數(shù) 一開(kāi)始是1是奇數(shù)
      que.push(p);
      while(!que.empty())
      {
          vector<int> vec;    //這個(gè)是局部變量否則每次都會(huì)把前邊的在輸出一遍
          int size=que.size();
          for(int i=0;i<size;i++)
          {
              //類(lèi)似于二叉樹(shù)的層次遍歷
              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)  //是偶數(shù)的時(shí)候要反轉(zhuǎn)
          {
              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存奇數(shù)層節(jié)點(diǎn)
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        s1.push(pRoot);
        //s2存偶數(shù)層節(jié)點(diǎn)
        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;
    }

上道題變形：把二叉樹(shù)打印成多行

題目描述：從上到下按層打印二叉樹(shù)，同一層結(jié)點(diǎn)從左至右輸出。每一層輸出一行。

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();   //每次都是一個(gè)新的隊(duì)列
              vector<int> vec;  //每次都是一個(gè)新的數(shù)組
              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;
      }
  
};