乐趣区

之字形打印二叉树

jiezi

[TOC]

题目描述

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

分析

拿到这道题目，首先我们可以确定的是应该用层次遍历法遍历二叉树，所以在解题之前我们先来回顾一下基于广度优先的二叉树的遍历是怎样的

顺便贴上层次遍历法遍历二叉树的代码 

  public ArrayList<Integer> level(TreeNode root){ArrayList<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()){TreeNode curNode = queue.pollFirst();
            list.add(curNode.val);
            if(curNode.left != null) queue.add(curNode.left);
            if(curNode.right != null) queue.add(curNode.right);
        }
        return list;
    }

错误示范

接下来我们分析这道题目，本道题其实和基本的层次遍历很像，只是当层数为奇数的时候是从左到右遍历，当层数为偶数的时候是从右到左遍历（自顶向下计数），所以我们容易想到的办法是能不能用一个全局层数计数器，当奇数层的时候，我们先添加左节点再添加右节点；当为偶数层的时候，我们先添加右节点再添加左节点

(ps: 这是错误方法)

public ArrayList<ArrayList<Integer>> Print1(TreeNode pRoot) {LinkedList<TreeNode> queue = new LinkedList<>();
        ArrayList<ArrayList<Integer>> listResult = new ArrayList<>();
        int count = 1;

        queue.add(pRoot);

        while (!queue.isEmpty()){ArrayList<Integer> list = new ArrayList<>();
            TreeNode curNode = queue.pollFirst();
            list.add(curNode.val);
            count++;
            if(count %2 == 0){if(curNode.right != null) queue.add(curNode.right);
                if(curNode.left != null) queue.add(curNode.left);
            }else {if(curNode.left != null) queue.add(curNode.left);
                if(curNode.right != null) queue.add(curNode.right);
            }
            listResult.add(list);
        }

        return listResult;
    }
 您的代码已保存
答案错误: 您提交的程序没有通过所有的测试用例
case 通过率为 0.00%

用例:
{8,6,10,5,7,9,11}

对应输出应该为:

[[8],[10,6],[5,7,9,11]]

你的输出为:

[[8],[10],[6],[9],[11],[7],[5]]

通过用例测试我们发现了用一个队列无法实现，count 并不能记录层数的奇偶性

正确示范

接下来我们采用两个栈来分别存储相邻两层的节点

  • 先将第一层压入栈 stack2
  • 然后将 stack2 中的元素依次出栈，并将其中的元素的左 -> 右节点分别压入栈 stack1
  • 同理，stack1 的元素依次出栈，并将其中的元素的右 -> 左节点依次压入栈 stack2
  • 依次循环

具体如下图所示

具体实现 

 public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if(pRoot == null)return list;// 注意考虑到空元素，并且此时返回 list，不是 null

        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack2.add(pRoot);
        while (!stack2.isEmpty() || !stack1.isEmpty()){ArrayList<Integer> subList = new ArrayList<>();
            if(!stack2.isEmpty()){
                // 需要将 stack2 中的元素全部弹出，此时才是该层的所有节点
                while (!stack2.isEmpty()){TreeNode curNode = stack2.pop();
                    subList.add(curNode.val);
                    // 弹出 stack2 中的元素的同时，需要将其中元素的左 -> 右节点压入栈 stack1
                    if(curNode.left != null) stack1.add(curNode.left);
                    if(curNode.right != null) stack1.add(curNode.right);
                }
                list.add(subList);
            } else {
                // 需要将 stack1 中的元素全部弹出，此时才是该层的所有节点
                while (!stack1.isEmpty()){TreeNode curNode1 = stack1.pop();
                    subList.add(curNode1.val);
                    // 弹出 stack1 中的元素的同时，需要将其中元素的右 -> 左节点压入栈 stack2
                    if(curNode1.right != null) stack2.add(curNode1.right);
                    if(curNode1.left != null) stack2.add(curNode1.left);
                }
                list.add(subList);
            }

        }

        return list;

    }

参考

《剑指 offer 纪念版》

退出移动版