# morris traversal

###### tags: `BST`

[173. Binary Search Tree Iterator](/ytl0bPnISjGFk4rSwjQRsQ)

1. spatial O(1)

two space cur and node point(son node)

使用輔助pointer 1. 創造連結

當cur的left為null 表示到達目前的值組最小值
遞迴cur為cur.right and break(藉由以下自行link)

當cur的left不為null=>需要鏈結cur.left到cur
鏈結cur.left的right most node之right到cur
cur=cur.left;

loop情況會有兩種
1. 持續創建cur.left right most node 到 cur(新建link)
2. 發現cur.left right most node 的right為cur(需要拆除link 同時表示左側已經loop完畢 遞迴cur=cur.right break loop;

遞迴cur為cur.right(藉由自行link)

2. time O(2N)

Morris 遍歷中每個節點會被訪問兩次，因此總時間複雜度為O(2n)=O(n)

		TreeNode cur, point;

		public BSTIterator(TreeNode root) {
			this.cur = root;
		}

		public int next() {
			int res = -1;
			point = cur;
			while (cur != null) {

				if (cur.left == null) {
					res = cur.val;
					cur = cur.right;
					break;
				} else {

					
					point = cur.left;
					//find rightest node or cycle
					while (point.right != null && point.right != cur) {
						point = point.right;
					}

					if (point.right == null) {
					//find rightest node and link	
						point.right = cur;
						cur = cur.left;
					} else {
					// read second time and delete the link
						res = cur.val;
						point.right = null;
						cur = cur.right;
						break;
					}

				}

			}
			return res;
		}

		public boolean hasNext() {
			return cur != null;
		}