剑指 Offer 32 - III. 从上到下打印二叉树 III-白红宇

剑指 Offer 32 - III. 从上到下打印二叉树 III

阅读量：4033 次

发布时间：2019-05-24

本文共 1349 字，大约阅读时间需要 4 分钟。

题目描述

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

例如:

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

9 20

15 7

返回其层次遍历结果：

[

[3],

[20,9],

[15,7]

]

提示：

节点总数 <= 1000

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

JAVA

双栈

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {
       public List
   
    
     > levelOrder(TreeNode root) {
                 List
     
      
       >  res=new  ArrayList<>();        if (root==null)            return  res;        Stack
       
         stack1=new Stack<>();  //奇数栈        Stack
        
          stack2=new Stack<>(); //偶数栈 int count=1; stack1.push(root); while(!stack1.isEmpty() || !stack2.isEmpty()){ if(count %2==1){ List
         
           temp1=new ArrayList<>(); while(!stack1.isEmpty()){ TreeNode top1=stack1.pop(); temp1.add(top1.val); if(top1.left!=null) stack2.push(top1.left); if(top1.right!=null) stack2.push(top1.right); } res.add(temp1); }else{ List
          
            temp2=new ArrayList<>(); while (!stack2.isEmpty()){ TreeNode top2=stack2.pop(); temp2.add(top2.val); if(top2.right!=null) stack1.push(top2.right); if(top2.left!=null ) stack1.push(top2.left); } res.add(temp2); } count++; } return res; }}