Python解法 利用层序和中序递归创建二叉树，然后递归打印叶子节点，morris 前序后序遍历二叉树 # -*- coding=utf-8 -*- class TreeNode(): def __init__(self, val): self.val = val self.left = None self.right = None class Solution(): def recreate_tree(self, level, mid_order): if not level or not mid_order: return None root = TreeNode(level[0]) root_index = mid_order.index(level[0]) left_mid_order = mid_order[:root_index] right_mid_order = mid_order[root_index+1:] left_level = [item for item in level if item in left_mid_order] right_level = [item for item in level if item in right_mid_order] root.left = self.recreate_tree(left_level, left_mid_order) root.right = self.recreate_tree(right_level, right_mid_order) return root def morris_pre_traverse(self, root): if root is None: return None cur = root most_right = None while cur: most_right = cur.left if most_right: while most_right.right and most_right.right != cur: most_right = most_right.right if most_right.right is None: most_right.right = cur # 第一次到达即打印 print(cur.val, end=' ') cur = cur.left continue else: most_right.right = None else: # 没有左子树的只会到达一次 print(cur.val, end=' ') cur = cur.right print('') def print_leaf(self, root): if not root.left and not root.right: print(root.val, end=' ') return if root.left: self.print_leaf(root.left) if root.right: self.print_leaf(root.right) def morris_post_traverse(self, root): if root is None: return None cur = root most_right = None while cur: most_right = cur.left if most_right: while most_right.right and most_right.right != cur: most_right = most_right.right if most_right.right is None: most_right.right = cur cur = cur.left continue else: most_right.right = None # 在第二次到达时逆序打印cur节点的左子树的右边界 self.print_edge(cur.left) cur = cur.right # 逆序打印整个二叉树的右边界 self.print_edge(root) print('') def print_edge(self, node): tail = self.reverse_edge(node) temp = tail while temp: print(temp.val, end=' ') temp = temp.right self.reverse_edge(tail) def reverse_edge(self, node): pre = None while node: next_node = node.right node.right = pre pre = node node = next_node return pre if __name__ == "__main__": level = list(map(int, input().split())) mid_order = list(map(int, input().split())) ex = Solution() root = ex.recreate_tree(level, mid_order) ex.print_leaf(root) print('') ex.morris_pre_traverse(root) ex.morris_post_traverse(root)