//不保留小数
func Sqrt(x int) int {

	if x <= 0 {
		return 0
	}

	l, r := 1, x-1
	for l <= r {
		mid := l + (r-l)>>1
		if mid > x/mid {
			r = mid - 1
		} else if mid < x/mid {  //Tips:写成x/mid用来确认不会溢出
			l = mid + 1
		} else {
			return mid
		}
	}

	return r
}

func MorrisPreOrderTraverse(root *TreeNode) []int {
	if root == nil {
		return nil
	}

	var mostRight *TreeNode
	cur := root
	var ret []int
	for cur != nil {
		//如果当前节点没有左子树
		if cur.Left == nil { //当前节点向右移动  (只有没有左子树的节点会走这一步)
			ret = append(ret, cur.Val)
			cur = cur.Right
		} else { //找到当前节点左子树的最右节点
			mostRight = cur.Left

			for mostRight.Right != nil && mostRight.Right != cur {
				mostRight = mostRight.Right
			}
			//此时mostRight就是当前节点左子树的最右节点
			if mostRight.Right == nil { //说明是第一次来到
				ret = append(ret, cur.Val)
				mostRight.Right, cur = cur, cur.Left
			} else { //说明是第二次来到(只有有左子树的时候才会有第二次来到)
				mostRight.Right, cur = nil, cur.Right
			}
		}
	}

	return ret
}

/** ✅
 * @Author: yirufeng
 * @Date: 2020/12/7 11:41 上午
 * @Desc:
 * 方法一：暴力
 * 方法二：从右上角或者左下角每次排除一行或者一列
 * 方法三：每一行二分搜索
 * 方法四：采用二分
		思路：获取当前搜索矩阵的中心点，然后排出左上角或者右下角的矩阵
	如下是方法四代码
 **/
func searchTarget(matrix [][]int, x1, y1, x2, y2, target int) bool {
	//递归可能越界
	if x1 > x2 || y1 > y2 {
		return false
	}

	//之前这个if语句块没有写会死循环，
	//注意点：避免x1，y1，x2，y2相等时调用searchTarget(matrix, x1, y1, xMid, yMid, target)死循环
	if x1 == x2 && y1 == y2 {
		if matrix[x1][y1] == target {
			return true
		}
		return false
	}

	//得到中心点坐标
	xMid, yMid := x1+(x2-x1)>>1, y1+(y2-y1)>>1
	if matrix[xMid][yMid] > target { //排除右下角
		return searchTarget(matrix, x1, y1, xMid, yMid, target) ||
			searchTarget(matrix, x1, yMid+1, xMid-1, y2, target) ||
			searchTarget(matrix, xMid+1, y1, x2, yMid-1, target)
	} else if matrix[xMid][yMid] < target { //排除左上角
		return searchTarget(matrix, x1, yMid+1, xMid, y2, target) ||
			searchTarget(matrix, xMid+1, y1, x2, yMid, target) ||
			searchTarget(matrix, xMid+1, yMid+1, x2, y2, target)
	}
	return true

}

func searchMatrix(matrix [][]int, target int) bool {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return false
	}
	return searchTarget(matrix, 0, 0, len(matrix)-1, len(matrix[0])-1, target)
}