每天一道leetcode-103二叉树的锯齿形层次遍历

• 2019 年 10 月 4 日
• 筆記

前言

今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426

昨天的题解

每天一道leetcode-103二叉树的锯齿形层次遍历

题目

题目详解

思路

• 剑指offer思路的实现，使用两个栈，具体看代码
• 比如第一层3的话那么下一层利用栈存入9和20，然后下一层的栈就是先弹出的就是20，然后是9，这样就实现了之字形打印。

代码

/**   * Definition for a binary tree node.   * public class TreeNode {   *     int val;   *     TreeNode left;   *     TreeNode right;   *     TreeNode(int x) { val = x; }   * }   */  class Solution {      public List<List<Integer>> zigzagLevelOrder(TreeNode root) {          TreeNode pRoot = root;          Stack<TreeNode> stack1 = new Stack<>();          Stack<TreeNode> stack2 = new Stack<>();          ArrayList<Integer> tempResult = new ArrayList<>();          List<List<Integer>>  resultList = new ArrayList<>();          if(pRoot == null)              return resultList;          int layerCount = 1;          stack1.push(pRoot);          while(!stack1.isEmpty() || !stack2.isEmpty())          {                while(!stack1.isEmpty())              {                  TreeNode tempNode = stack1.pop();                  if(tempNode.left != null)                  {                      stack2.push(tempNode.left);//stack2中按照先左后右的方式入栈，                  }//那么下一层就是按照先右后左出栈，完成之字形。                  if(tempNode.right != null)                      stack2.push(tempNode.right);                  tempResult.add(tempNode.val);                  if(stack1.isEmpty())                  {//stack1为空，说明stack1中存的这些节点打印完了，所以要把这一层的节点内容存入结果中                      resultList.add(new ArrayList<Integer>(tempResult));                      tempResult.clear();                  }              }              while(!stack2.isEmpty())              {//这里大体思路和上面相同，要注意的就是由于上一层已经是逆序打印                  TreeNode tempNode = stack2.pop();//所以这一层必须先右后左入栈，才能确保是顺序打印                  if(tempNode.right != null)                  {                      stack1.push(tempNode.right);                  }                  if(tempNode.left != null)                      stack1.push(tempNode.left);                  tempResult.add(tempNode.val);                  if(stack2.isEmpty())                  {                      resultList.add(new ArrayList<Integer>(tempResult));                      tempResult.clear();                  }              }          }          return resultList;      }  }