3.2 打印二叉树的边界节点 I 程序员代码面试指南

题目 【3.2 打印二叉树的边界节点 I】给定一棵二叉树的头节点 head，按照如下两种标准分别实现二叉树边界节点的逆时针打印。
标准:

1.头节点为边界节点。
2.叶节点为边界节点。 3.如果节点在其所在的层中是最左的或最右的，那么该节点也是边界节点。

例如，如图 3-2 所示的树。

文章图片

按标准1的打印结果为:

1，2，4，7，11，13，14，15，16，12，10，6，3

代码

class Node: def __init___(self, data): self.right = None self.left = None self.val = datadef printEdge(head: Node): if head is None: return # 获取树的深度 height = get_height(head, 0)edgeMap = [[None, None] * height] # 设置左右边界的数组 setEdgeMap(h, 0, edgeMap) # 打印左边界节点 for i in range(len(edgeMap)): if edgeMap[i][0] != edgeMap[i][1]: print(edgeMap[i][0].value, " ") # 打印不在左右边界的叶子节点 printLeafNotInMap(head, 0, edgeMap) # 打印右边界节点 for i in range(len(edgeMap)-1, -1, -1): if edgeMap[i][0] != edgeMap[i][1]: print(edgeMap[i][1].value, " ") print("\n")def setEdgeMap(h, l, edgeMap): if h is None: return None edgeMap[l][0] = h if edgeMap[0] is None else edgeMap[0] edgeMap[l][1] = h setEdgeMap(h.left, l+1, edgeMap) setEdgeMap(h.right, l+1, edgeMap)def get_height(head, l): if h is None: return l return max(get_height.left, l+1), get_height(head.right, l+1))def printLeafNotInMap(head, l, m): if h is None: return if h.left is None and h.right is None and h != m[l][0] and h!=m[l][0]: print(h.value, " ") printLeafNotInMap(h.left, l+1, m) printLeafNotInMap(h.right, l+1, m)