美文网首页剑指offer的java实现-数据结构与算法
剑指offer第二版-32.3.之字形打印二叉树

剑指offer第二版-32.3.之字形打印二叉树

作者: ryderchan | 来源:发表于2017-08-31 11:00 被阅读206次

    本系列导航:剑指offer(第二版)java实现导航帖

    面试题32.3:之字形打印二叉树

    题目要求:
    请实现一个函数按照之字形打印二叉树。即第一层从左到右打印,第二层从右到左打印,第三层继续从左到右,以此类推。

    解题思路:
    第k行从左到右打印,第k+1行从右到左打印,可以比较容易想到用两个栈来实现。
    另外要注意,根据是从左到右还是从右到左访问的不同,压入左右子节点的顺序也有所不同。

    package structure;
    import java.util.LinkedList;
    import java.util.Queue;
    /**
     * Created by ryder on 2017/6/12.
     * 树节点
     */
    public class TreeNode<T> {
        public T val;
        public TreeNode<T> left;
        public TreeNode<T> right;
        public TreeNode(T val){
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }
    
    package chapter4;
    import structure.TreeNode;
    import java.util.Stack;
    /**
     * Created by ryder on 2017/7/18.
     * 之字形打印二叉树
     */
    public class P176_printTreeInSpecial {
        public static void printTreeInSpeical(TreeNode<Integer> root){
            if(root==null)
                return;
            Stack<TreeNode<Integer>> stack1 = new Stack<>();
            Stack<TreeNode<Integer>> stack2 = new Stack<>();
            TreeNode<Integer> temp;
            stack1.push(root);
            while(!stack1.isEmpty() || !stack2.isEmpty()){
                if(!stack1.isEmpty()) {
                    while (!stack1.isEmpty()) {
                        temp = stack1.pop();
                        System.out.print(temp.val);
                        System.out.print('\t');
                        if (temp.left != null)
                            stack2.push(temp.left);
                        if (temp.right != null)
                            stack2.push(temp.right);
                    }
                }
                else {
                    while (!stack2.isEmpty()) {
                        temp = stack2.pop();
                        System.out.print(temp.val);
                        System.out.print('\t');
                        if (temp.right != null)
                            stack1.push(temp.right);
                        if (temp.left != null)
                            stack1.push(temp.left);
                    }
                }
                System.out.println();
            }
        }
        public static void main(String[] args){
            //            1
            //          /   \
            //         2     3
            //       /  \   / \
            //      4    5 6   7
            TreeNode<Integer> root = new TreeNode<Integer>(1);
            root.left = new TreeNode<Integer>(2);
            root.right = new TreeNode<Integer>(3);
            root.left.left = new TreeNode<Integer>(4);
            root.left.right = new TreeNode<Integer>(5);
            root.right.left = new TreeNode<Integer>(6);
            root.right.right = new TreeNode<Integer>(7);
            printTreeInSpeical(root);
        }
    }
    

    运行结果

    1111
    

    相关文章

      网友评论

        本文标题:剑指offer第二版-32.3.之字形打印二叉树

        本文链接:https://www.haomeiwen.com/subject/qmpwdxtx.html