【面试】反转二叉树 binary tree 面试

问题
任意给一个二叉树，使之左右镜像反转。

文章图片

这是一个经典面试题，考察tree这种数据结构的构建和递归操作。

class Node(object): def __init__(self, val): self.val = val.astype(np.int32) self.left = None self.right = Nonedef create_subtree(n_layers, vals, layer): '''Inputs a list `vals` to provide the values for the tree nodes. It assumes that `vals` contains enough elements to fill all the Nodes of this tree, and takes the element in the middle of this list `vals` to build the current Node. ''' if layer >= n_layers: return None pivot = len(vals) // 2 root = Node(vals[pivot]) root.left = create_subtree(n_layers, vals[:pivot], layer + 1) root.right = create_subtree(n_layers, vals[pivot+1:], layer + 1) return rootdef swap_subtree(node): if node is None: return node.left = swap_subtree(node.left) node.right = swap_subtree(node.right) node.right, node.left = node.left, node.right return nodedef main(): n_layers = 5 vals = np.array(range(0, 100)) bt = create_subtree(n_layers, vals, 0) bt_swap = swap_subtree(bt)

【【面试】反转二叉树 binary tree】以上main()函数给出一个测试用例。测试结果的动画贴在本文的头部。