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)