二叉树基本概念

面试的时候提到的树, 大部分都是二叉树. 所谓二叉树是树的一种特殊结构, 在二叉树中每个节点最多只能有两个子节点, 在二叉树中最重要的操作莫过于遍历, 即按照某一顺序访问树中的所有节点.

树的遍历方式

通常树有如下几种遍历方式:

1. 前序遍历
2. 中序遍历
3. 后续遍历

每种遍历都对应三种实现方式, 基于递归和迭代(循环)实现的时间复杂度为\(O(n)\), 空间复杂度为\(O(n)\), 基于Morris算法的时间复杂度为\(O(n)\), 空间复杂度为\(O(1)\). (应聘者应该对这三种遍历的9种实现方式都了如指掌)

Morris通用解法

Morris遍历使用二叉树节点中大量指向null的指针, 由Joseph Morris 于1979年发明, Morris的通用解法过程如下:

Morris的整体思路为: 以某个跟节点出发, 找到它的左子树的最右侧节点之后与这个跟节点进行连接. 由右图, 建立连接之后, cur这个指针可以完整的聪一个节点顺着下一个节点遍历, 将整颗树遍历完毕, 直到7这个节点右侧没有指向.