美团视觉算法工程师之 AR/VR 面试 题 3 道答案

1.1 编程题

• ①给你一个有序数组，请构建一棵 二叉树 ；
• ②中序输出该 二叉树 ；
• ③求树的深度；
  解析：

根据题目描述考察的是 leetcode 中的”将有序数组转换为二叉搜索树“题；
二叉搜索树的中序遍历是有序序列，可以确保数组是二叉搜索树的中序遍历序列，然后依次重建二叉
树（如果没有别的要求，则重建的二叉树不唯一），此处给出平衡二叉树的一种解法：

1. class TreeNode：
2. def __init__(self, val=0, left=None, right=None)：
3. self.val = val
4. self.left = left
5. self.right = right
6. def sortedArrayToBST(nums)：
7. def helper(left, right)：
8. if left > right：
9. return None
10. # 总是选择中间位置左边的数字作为根节点
11. mid = (left + right) // 2
12. root = TreeNode(nums[mid])
13. root.left = helper(left, mid - 1)
14. root.right = helper(mid + 1, right)
15. return root
16. return helper(0, len(nums) - 1

创建的二叉树为:

中序输出二叉树：

遍历二叉树时，根据根节点的位置，可以分为前序遍历、中序遍历、后续遍历 3 种；
中序遍历即按照 左子树 => 根节点 => 右子树 的顺序遍历二叉树，左右子树遍历依然遵循这个顺序
，直至遍历完整课树；

代码逻辑：
inorder(root) 表示当前遍历到 root 节点的值，然后递归调用 inorder(root.left) 遍历 root 节点的
左子树，再递归调用 inorder(root.right) 遍历 root 节点的右子树，root 节点是空节点时递归终止。参考
代码如下：

1. def inorderTraversal(root)：
2. def inorder(root, ret)：
3. if not root： return
4. inorder(root.left, ret)
5. ret.append(root.val)
6. inorder(root.right, ret)
7.
8. ret = []
9. inorder(root, ret)
10. return ret

计算深度：
分别计算左右子树的深度，然后选取最大的作为树的深度，使用递归遍历左右子树；参考代码如下：

1. def calDepth(root)：
2. if root is None：
3. return 0
4. else：
5. left_depth = calDepth(root.left)
6. right_depth = calDepth(root.right)
7. return max(left_depth, right_depth) + 1

以上完成代码如下，可以在本地电脑运行：

1. class TreeNode：
2. def __init__(self, val=0, left=None, right=None)：
3. self.val = val
4. self.left = left
5. self.right = right
6.
7. def sortedArrayToBST(nums)：
8. def helper(left, right)：
9. if left > right：
10. return None
11. # 总是选择中间位置左边的数字作为根节点
12. mid = (left + right) // 2
13.
14. root = TreeNode(nums[mid])
15. root.left = helper(left, mid - 1)
16. root.right = helper(mid + 1, right)
17. return root
18.
19. return helper(0, len(nums) - 1)
20.
21. def inorderTraversal(root)：
10
22.
23. def inorder(root, ret)：
24. if not root： return
25. inorder(root.left, ret)
26. ret.append(root.val)
27. inorder(root.right, ret)
28.
29. ret = []
30. inorder(root, ret)
31. return ret
32.
33. def calDepth(root)：
34. if root is None：
35. return 0
36. else：
37. left_depth = calDepth(root.left)
38. right_depth = calDepth(root.right)
39. return max(left_depth, right_depth) + 1
40. if __name__ == "__main__"：
41. nums = [-10,-3,0,5,9]
42. # 构建二叉树
43. tree = sortedArrayToBST(nums)
44. # 中序遍历
45. ret = inorderTraversal(tree)
46. print(ret)
47. # 二叉树深度
48. depth = calDepth(tree)
49. print(depth)