之字形打印二叉树（Java 递归实现）

深藏阁楼爱情的钟 2022-05-17 03:51 220阅读 0赞

> 分析：  
> 按照之字形打印，可以认为奇数层从左向右打印，偶数层从右向左打印  
> 同时，本次最先访问到的结点的子节点信息在下一次打印时为最后打印，符合先进后出的逻辑，故可以使用栈来完成

**结点类：**

class TreeNode{ 
    
        int val;//当前节点value
        TreeNode left;//左儿子
        TreeNode right;//右儿子
    
        public TreeNode(int val) {
            this.val = val;
        }
    }

输出方法具体实现：

public static void print(TreeNode root){
    
            if (root == null) {
                System.out.println("该树为null");
                return;
            }
            int level = 1;//从根节点第一层遍历
            Stack<TreeNode> stackOne = new Stack<>();//用来记录当前遍历的层结点
            stackOne.push(root);
            printTree(level,stackOne);
        }
    
        /** * 递归遍历整个树 * @param level 当前树的层次 * @param from 当前层的所有结点信息 */
        public static void printTree(int level,Stack<TreeNode> from){
            if (from == null || from.empty()) {
                return;
            }
    
            //用来存储下一层所有结点的信息
            Stack<TreeNode> to = new Stack<>();
    
            System.out.print(level+" : ");
            //当前层次为奇数，从左向右遍历
            if (level %2 != 0) {
                while(!from.empty()){
                    TreeNode node = from.pop();
                    if (node != null) {
                        System.out.print(node.val+"\t");
                        if (node.left != null) {
                            to.push(node.left);
                        }
                        if (node.right != null) {
                            to.push(node.right);
                        }
                    }
                }
            }else{
    
                //当前为偶数层，需要从右向左遍历
                while(!from.empty()){
                    TreeNode node = from.pop();
                    //当前节点不为null，或者不是叶子结点
                    if (node != null) {
                        System.out.print(node.val+"\t");
                        if (node.right != null) {
                            to.push(node.right);
                        }
                        if (node.left != null) {
                            to.push(node.left);
                        }
                    }
                }
    
            }
    
            System.out.println();
            //递归
            printTree(++level,to);
        }

测试：

public static void main(String[] args) {
            TreeNode root = new TreeNode(1);
            TreeNode one = new TreeNode(2);
            TreeNode two = new TreeNode(3);
            TreeNode three = new TreeNode(4);
            TreeNode four = new TreeNode(5);
            TreeNode five = new TreeNode(6);
            TreeNode six = new TreeNode(7);
    
            root.left=one;
            root.right=two;
            one.left=three;
            one.right=four;
            two.left=five;
            two.right=six;
    
            print(root);
    
        }

输出结果：

1 : 1   
    2 : 3   2   
    3 : 4   5   6   7