简介

上篇文章使用LeetCode方式初始化二叉树介绍了如何使用更简单的方式在LeetCode中初始化二叉树，这篇文章又有了新的问题：经过一顿操作(LeetCode自己实现的函数)，如何验证自己的函数是不是对的呢？难道说每次验证都写一遍层序遍历？或是前、中、后序遍历？那岂不是太难受了。别担心，本文通过重写二叉树(TreeNode)的toString方法来实现二叉树的层序遍历打印。

LeetCode官方案例

对于下图的二叉树

image.png

我们想验证我们构造出来的二叉树是否就是图中的二叉树，但是直接打印二叉树的结果如下：

// 构造TreeNode
val root = TreeNode(1, 2, null, 3)

// 打印TreeNode
println(root)

// 输出结果
leetcode.TreeNode@327471b5

我们并不能直观的看到二叉树的数据是否就是我们期待的样子，下面展示使用中序遍历打印二叉树的代码:

// 中序遍历
private fun inorder(root: TreeNode?) {
    if (root == null) return
    inorder(root.left)
    println(root.`val`)
    inorder(root.right)
}

// 打印二叉树
inorder(TreeNode(1, 2, null, 3))

// 输出结果
3
2
1

可以发现，我们并不能直观的感受到二叉树的正确结构，前序和后续也类似。那让我们再试试层序遍历：

// 层序遍历
private fun levelOrder(root: TreeNode?) {
    val queue = LinkedList<TreeNode?>()
    queue.offer(root)
    var level = 1
    while (queue.isNotEmpty()) {
        val size = queue.size
        print("第${level++}层:")
        for (i in 0 until size) {
            val node = queue.pop()
            print("${node?.`val`}, ")
            if (node != null) {
                queue.offer(node.left)
                queue.offer(node.right)
            }
        }
        println()
    }
}

// 打印二叉树
levelOrder(TreeNode(1, 2, null, 3))

// 输出结果
第1层:1, 
第2层:2, null, 
第3层:3, null, 
第4层:null, null, 

好像比较清晰了，但是如果能直接打印出1, 2, null, 3，那岂不是一眼就能看出来？我们可以通过覆写toString方法来实现这点，同样适用层序遍历，代码如下：

private fun toArray(): List<Int?> {
    val arr = ArrayList<Int?>()
    val queue = LinkedList<TreeNode?>()
    queue.offer(this)
    while (queue.isNotEmpty()) {
        val size = queue.size
        for (i in 0 until size) {
            val temp = queue.pop()
            arr.add(temp?.`val`)
            if (temp != null) {
                queue.offer(temp.left)
                queue.offer(temp.right)
            }
        }
    }
    while (arr.last() == null) {
        arr.removeAt(arr.lastIndex)
    }
    return arr
}
override fun toString() = toArray().toString()

// 打印二叉树
println(TreeNode(1, 2, null, 3))

// 输出结果
[1, 2, null, 3]

代码解释

整个程序遍历的过程(while循环)在上一篇文章以及本文前段都有详细的说明，这里就不在重复说了,我们通过层序遍历将所有节点保存在数组中，与LeetCode中的demo对比发现LeetCode还省略了末尾的null值，方便看的更简洁，所以最后使用一个while循环去除多余的null。

总结

结合上一篇文章，我们分别实现了基于LeetCode二叉树的构造方法以及toString方法，是不是对整个LeetCode的刷题过程有不小的速度提升呢，下面是完成的TreeNode代码：

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null

    constructor(v0: Int, vararg v: Int?) : this(v0) {
        val queue = LinkedList<TreeNode?>()
        var index = -1
        queue.offer(this)
        while (queue.isNotEmpty()) {
            val size = queue.size
            for (i in 0 until size) {
                val temp = queue.pop()
                if (temp != null) {
                    index++
                    if (index < v.size && v[index] != null) {
                        temp.left = TreeNode(v[index]!!)
                    }
                    index++
                    if (index < v.size && v[index] != null) {
                        temp.right = TreeNode(v[index]!!)
                    }
                    queue.offer(temp.left)
                    queue.offer(temp.right)
                }
            }
        }
    }

    // 层序遍历，并保存在一个数组中，并删除尾部多余null
    private fun toArray(): List<Int?> {
        val arr = ArrayList<Int?>()
        val queue = LinkedList<TreeNode?>()
        queue.offer(this)
        while (queue.isNotEmpty()) {
            val size = queue.size
            for (i in 0 until size) {
                val temp = queue.pop()
                arr.add(temp?.`val`)
                if (temp != null) {
                    queue.offer(temp.left)
                    queue.offer(temp.right)
                }
            }
        }
        while (arr.last() == null) {
            arr.removeAt(arr.lastIndex)
        }
        return arr
    }

    override fun toString() = toArray().toString()
}

如果你使用的是gradle构建工程，可以直接引入我的LeetCode项目代码
希望本文能够帮到你。^ - ^