方法一:二分
- 时间复杂度:O(logN)
- 空间复杂度:O(1)
注意点:
mid*mix > x
的时候容易溢出,改成mid > x/mid
mid := (l+r)>>1
的时候也容易溢出,改成mid := l + (r-l)>>1
不保留小数
1 | //不保留小数 |
注意点:
mid*mix > x
的时候容易溢出,改成mid > x/mid
mid := (l+r)>>1
的时候也容易溢出,改成mid := l + (r-l)>>1
1 | //不保留小数 |
优点:不同于我们之前递归遍历或者借助栈来进行树的遍历,因为Morris遍历可以在保证时间复杂度依然为O(N)的情况下可以将空间复杂度降低为O(1)
假设当前节点为cur,最一开始来到树根,什么时候停呢,当cur来到nil的时候就停止
遍历之后发现一个问题:任何一个节点,只要有左孩子Morris遍历的时候会遍历两次,也就是有左树的节点,左树不为空,首先遍历当前节点,然后遍历左树,遍历之后再回到当前节点,所以当前节点会遍历两次。因为用这个就可以知道是第一次来到自己还是第二次来到自己。
第一次遍历到该节点的时候直接打印(没有左子树的节点会遍历到一次,有左子树的节点会遍历到两次,但是我们第一次就应该打印)
1 | func MorrisPreOrderTraverse(root *TreeNode) []int { |
套路总结
注意:方法一二代码较为简单,这里就不再赘述了
上图中的方法三,我们以LeetCode 240为例
1 | /** ✅ |
1 / 3