Morris 遍历

中序遍历

前言:

​ 我们在中序遍历的时候,一定先遍历左子树,然后遍历当前节点,最后遍历右子树。在常规方法中,我们用递归回溯或者是栈来保证遍历完左子树可以再回到当前节点,但这需要我们付出额外的空间代价。我们需要用一种巧妙地方法可以在 O(1) 的空间下,遍历完左子树可以再回到当前节点。我们希望当前的节点在遍历完当前点的前驱之后被遍历,我们可以考虑修改它的前驱节点的 r i g h t right right