[LeetCode]Reaching Points

从题目的意思中就可看出来，给定了root和target，这是一个二叉树找节点的问题，DFS是一个方法，但是考虑到输入的范围，时间复杂度肯定太大，我们需要换一个方法。DP也是一个很容易想到的优化，DP[i][j]表示能否从初始节点达到(i, j)，我们有递推公式：

• DP[i][j] = DP[i - j][j] if i > j
• DP[i][j] = DP[i][j - 1] if j > i

但是因为输入太大显然没有足够的空间。但是这给我们提供了另外一个思路，那就是从target开始去搜root，以为给定的起始和目标点xy轴都是大于0的，那代表如果我们从target回溯找父节点，我们每次找到的是唯一的，只有一种可能，我们要保证父节点的坐标也都大于0。那么从target开始找起始点就可以让时间复杂度大大减小，假设目标节点为(x, y)，时间复杂度为O(max(x, y))，因为最坏的情况可以是(1, 1000000000)，从这个wosrt case来看应该还是过不了所有test case，但是我们先给出代码，之后再考虑优化：

可以看出这个算法的瓶颈在于如果x和y相差的太多，那么时间复杂度还是很高。那么我们完全可以缩短这个过程，不需要y -= x或者x-=y，直接x%=y, y%=x即可，同时注意答案是否在(x, [y % x, y])或者([x, x%y], y)的范围中即可。时间复杂度O(log(max(x, y)))，分析和Euclid Algorithm也即是求GCD的辗转相除法是一样的，具体可以参考这个分析。代码如下：