题目

有一棵二叉树，请设计一个算法，按照层次打印这棵二叉树。

给定二叉树的根结点root，请返回打印结果，结果按照每一层一个数组进行储存，所有数组的顺序按照层数从上往下，且每一层的数组内元素按照从左往右排列。保证结点数小于等于500。

思路

使用队列和两个变量，如图（其实需要一个变量来指向当前打印的元素）。

首先last=root（1），将root（1）入队，然后出队并打印，再用一个变量（temp）记录打印的元素。然后将root（1）的两个孩子（2和3）结点分别入队，入队的同时，让nlast指向两个孩子结点，即入队就更新nlast。

然后此时比较打印的元素（1）是否和last指向的元素（1）相同，若相同表示要换行了（因为last始终指向正在打印的当前行最右的元素），则更新last=nlast（last指向结点3），然后将结点2出队并打印，让temp更新并记录结点2，并将结点2的孩子结点（4）入队，并将nlast指向结点2的孩子结点（4），然后将结点（3）出队并打印，让temp更新并记录结点3，让结点（3）的孩子结点（5和6）入队，此时比较temp结点和last指向的结点（3）是否相同，相同则更新last=nlast，依次下去，即可完成打印。

Java代码

import java.util.*;


public class TreePrinter {
    // 结点定义
    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }    
    public int[][] printTree(TreeNode root) {
        // 在Java中LinkedList实现了Queue接口。
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode last, nlast = null;
        last = root; // 初始化last结点
        queue.add(last);  // 根节点入队
        // 结果要返回int[][],但不清楚需要几行几列，所以需要用到集合，这里相当于定义了一个二维数组
        // <>表示泛型，表示这个集合只能装Integer类型，可以忽略，因为编译之后泛型就没了
        List<List<Integer>> res = new ArrayList<>();
        // 定义每一行,即row作为res的元素
        List<Integer> row = new ArrayList<>();
        // 通过上面分析可以看到循环的条件是队列不为空，因为初始已经将根节点入队了
        while (!queue.isEmpty()) {
            // 结点首先出队，并用temp变量记录。
            TreeNode temp = queue.poll();
            // 这个可以使用不换行的打印，为了满足题目的返回条件，这里将它加入到行集合中
            row.add(temp.val);
            // 出队元素的左孩子不为空，入队并跟新nlast
            if (temp.left != null) {
                nlast = temp.left;
                queue.add(nlast);
            }
            // 出队元素的右孩子不为空，入队并跟新nlast
            if (temp.right != null) {
                nlast = temp.right;
                queue.add(nlast);
            }
            // 如果已经出队并被打印的元素和last指向的元素相同
            // 则需要换行了，并更新last=nlast
            if (temp.val == last.val) {
                last = nlast;
                // 将这一行加入到结果集合中
                res.add(row);
                // 清空这一行,这里不能用row.clear()，需要重新new一个对象出来。
                row = new ArrayList<>();
            }
        }
        // 到此结果就被遍历出来了，下面构造符合题目返回结果的元素。
        // 首先开辟多上行的元素，列是空的
        int [][] ans = new int[res.size()][];
        for (int i = 0; i < res.size(); i ++){
            // 元素对每一行开辟多少列
            ans[i] = new int[res.get(i).size()];
            for (int j = 0; j < res.get(i).size(); j++) {
                // 完成赋值
                ans[i][j] = res.get(i).get(j);
                // 测试使用
                //System.out.print(ans[i][j]);
            }
            // 测试使用
            //System.out.println();
        }
        //返回结果
        return ans;
    }
}

测试程序

public static void main(String[] args) {
    TreeNode root = new TreeNode(1);
    root.left = new TreeNode(2);
    root.right = new TreeNode(3);
    root.left.left = new TreeNode(4);
    root.right.left = new TreeNode(5);
    root.right.right = new TreeNode(6);
    root.right.left.left = new TreeNode(7);
    root.right.left.right = new TreeNode(8);
    printTree(root);
}

Python代码

# -*- coding:utf-8 -*-
# 结点定义 
class TreeNode:
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None

class TreePrinter:
    def printTree(self, root):
        # 结果定义
        res=[]  
         # 队列（使用列表可以模拟队列）
        queue=[] 
        # 判空
        if root==None:
            return res
        # 初始化结点
        last=nlast=root
        # 入队使用append()函数
        queue.append(root)
        # 一行，相当于Java代码中的row数组
        row=[]
        # 队列不为空用循环
        while len(queue):
            # 出队，并用temp结点来记录，使用pop(0)函数，即弹出列表的第一个元素（队首元素）
            temp=queue.pop(0)
            # 入队
            row.append(temp.val)
            # 如果出队元素的左右孩子不为空，则入队并更新nlast
            if temp.left!=None:
                queue.append(temp.left)
                nlast=temp.left
            if temp.right!=None:
                queue.append(temp.right)
                nlast=temp.right
            # 如果出队元素和last指向的元素相同，则完成一行的打印
            if temp==last:
                # 加入到结果中row[:]表示将row中所有元素放入到res中,是一个列表
                res.append(row[:])
                # 清空这一行
                row=[]
                # 更新last指向nlast
                last=nlast
         return res

上一篇：字符串-旋转词

下一篇：粗糙表面计算机模拟(matlab+3dsMax仿真)