LeetCode - The World's Leading Online Programming Learning Platform

Intuition

Build a tree with all conditions and traverse it through DFS to find the answer.

Approach

Step1. Build the tree

Since the robot has only two possible moves for the next step, right or down, we can construct a binary tree.

Each node represents a grid between the robot and the endpoint. The left subtree indicates moving down, and the right subtree indicates moving right.

When a node is 1 * 1, it means that the robot has reached the endpoint. If any value in a node is 0, it means that the robot has gone out of bounds.

Here is the tree and its annotations.

Setp2. Handle base cases

• When the node is 1*1, return 1, indicating that there is 1 way to reach the destination.
• When any value of the node is 0, return 0, indicating that there is no way to reach the destination on this path.

Setp3. Handle recursive cases

Return the sum of the values of the left subtree and the right subtree

Setp4. Cache

We use hash map to cache nodes.