【0】
前言
这是今天我从同事跳槽到快手一面的一个题目,虽然不是太难,但是听说也是卡了好半天,抽空大家不妨也作为饭后甜点看看(^o^)/~
个人感觉这属于那种见过就一定会的那种题目,如果没太接触过这种类似leetcode题目的话,还是得想一会儿的
下面咱们来一起看看,从题目出发…
【1】
题目
要求按照下面的格式将树信息打印出来,看着很是直观的打印结果

要求输出格式
A -> 第一行 B C -> 第二行 D E F -> 第三行 G H -> 第四行
就是按照给定的格式进行结点的打印
【3】
解决方案
很明显的可以看到,在实现该结果的同时,大致解决思路一定是基于过去咱们看到过的层次遍历的方式
在层次遍历的同时,记录每次换行操作时候的动作
在这所有之前,咱们先给出来结点信息,以便后面清楚的对图中二叉树进行操作
【利用Python看,简单又直观】
class TreeNode: def __init__(self, value): self.val = value # 结点值 self.left = None # 指向做孩子 self.right = None # 指向右孩子
需要回顾层次遍历代码的可以翻到文末,进行了层次遍历的展现,这里有过去用C语言实现的代码
由于题目中要求在打印结点信息的同时,要求给出结点所在行和列的信息
利用层次遍历遍历的特点(重点!重点!重点!在当前层的所有结点元素入队之后,上一层最后一个结点元素才会弹出),初始化两个指针 last 和 cur
- last 指向上一层最右侧结点
- cur 是当前结点位置【往队列中输入的结点】
只有当弹出的元素 与 last 指向的结点相同,说明 cur 也遍历到了当前层的最右面。此时,可以令 last = cur
具体细节流程,看下面[长长长长长…]图

以上,基于给定的树状结构进行了细致的说明,供大家参考。另外个人不太喜欢动图,原因是想要看清楚每一步的时候,不容易控制
对于队列的操作,利用 Python 的 list 数据结构实现的方式如下
# 入队 list.append('A') # 出队 list.append(0)
下面给出完整代码,并且给出构造树的代码已经层次遍历的代码
可以直接贴到自己的环境中进行实现
# -*- coding:utf-8 -*- # !/usr/bin/env python # 树结点类 class TreeNode: def __init__(self, value): self.val = value self.left = None self.right = None def level_order_traverse(root): if not root: return # 队列queue queue = [root] while len(queue) > 0: node = queue.pop(0) print(node.val, end=" ") if node.left: queue.append(node.left) if node.right: queue.append(node.right) def level_order_traverse_datail(root): last, n_last = root, root i = 1 if not root: return # 队列queue queue = [root] while len(queue) > 0: node = queue.pop(0) print(node.val, end=" ") if node.left: n_last = node.left queue.append(node.left) if node.right: n_last = node.right queue.append(node.right) # 当弹出的结点是last指向的结点时,令 last = n_last if last is node: last = n_last print(" -> 第 %d 行" % i) i = i + 1 if __name__ == "__main__": # 新建节点 node_A = TreeNode("A") node_B = TreeNode("B") node_C = TreeNode("C") node_D = TreeNode("D") node_E = TreeNode("E") node_F = TreeNode("F") node_G = TreeNode("G") node_H = TreeNode("H") # 构建二叉树 # A # / \ # B C # / / \ # D E F # / \ # G H node_A.left, node_A.right = node_B, node_C node_B.left = node_D node_C.left, node_C.right = node_E, node_F node_E.left, node_E.right = node_G, node_H # 打印结点元素 print("层次遍历结果:") level_order_traverse(node_A) print("\n层次遍历结果(打印行号):") level_order_traverse_datail(node_A)
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/2305/
转载文章受原作者版权保护。转载请注明原作者出处!