2096. Step-By-Step Directions From a Binary Tree Node to Another

class Solution {
    Map<TreeNode, TreeNode> parentMap = new HashMap<>();
    Set<TreeNode> visited = new HashSet<>();
    TreeNode startNode, endNode;

    public String getDirections(TreeNode root, int startValue, int destValue) {
        recordParents(root, new TreeNode(0), startValue, destValue);
        StringBuilder ans = new StringBuilder();
        findPath(startNode, ans);
        return ans.toString();
    }

    private void recordParents(TreeNode node, TreeNode parent, int startValue, int endValue) {
        if (node == null) {
            return;
        }
        if (node.val == startValue) {
            startNode = node;
        } else if (node.val == endValue) {
            endNode = node;
        }
        parentMap.put(node, parent);
        recordParents(node.left, node, startValue, endValue);
        recordParents(node.right, node, startValue, endValue);
    }

    private boolean findPath(TreeNode node, StringBuilder sb) {
        if (node == null || visited.contains(node)) {
            return false;
        }
        // Found the end node
        if (node == endNode) {
            return true;
        }

        visited.add(node);
        // Find left
        sb.append('L');
        boolean foundEndNode = findPath(node.left, sb);
        if (foundEndNode) {
            return true;
        }
        sb.deleteCharAt(sb.length() - 1);

        // Find right
        sb.append('R');
        foundEndNode = findPath(node.right, sb);
        if (foundEndNode) {
            return true;
        }
        sb.deleteCharAt(sb.length() - 1);

        // Find parent
        sb.append('U');
        foundEndNode = findPath(parentMap.get(node), sb);
        if (foundEndNode) {
            return true;
        } else {
            sb.deleteCharAt(sb.length() - 1);
            visited.remove(node);
            return false;
        }

    }

}

Brute force. 把parent先记录下来, 然后从起点DFS去终点.

class Solution {
    public String getDirections(TreeNode root, int startValue, int destValue) {
        StringBuilder startNodeRoute = new StringBuilder(), endNodeRoute = new StringBuilder();
        TreeNode startNode = findNode(root, startValue, startNodeRoute);
        TreeNode endNode = findNode(root, destValue, endNodeRoute);
        int commonPrefixEnd = 0, minLength = Math.min(startNodeRoute.length(), endNodeRoute.length());
        while (commonPrefixEnd < minLength
                && startNodeRoute.charAt(commonPrefixEnd) == endNodeRoute.charAt(commonPrefixEnd)) {
            commonPrefixEnd += 1;
        }
        return "U".repeat(startNodeRoute.length() - commonPrefixEnd)
                + endNodeRoute.substring(commonPrefixEnd).toString();

    }

    // 去的时候加工, 找到后一路回的过程也能加工
    private TreeNode findNode(TreeNode node, int target, StringBuilder sb) {
        if (node == null) {
            return null;
        }
        if (node.val == target) {
            return node;
        }

        sb.append('L');
        TreeNode findLeftTree = findNode(node.left, target, sb);
        if (findLeftTree != null) {
            return findLeftTree;
        }
        sb.deleteCharAt(sb.length() - 1);

        sb.append('R');
        TreeNode findRightTree = findNode(node.right, target, sb);
        if (findRightTree != null) {
            return findRightTree;
        }
        sb.deleteCharAt(sb.length() - 1);
        return findRightTree;
    }

    // 第二种构建route的方式, 我们是走一步记录一下走的什么, 自顶向下. 这个是找到node后, 从下到上一个个构建route,
    // 这样的route是反着的, 因此需要reverse.
    private boolean find(TreeNode n, int val, StringBuilder sb) {
        if (n.val == val)
            return true;
        if (n.left != null && find(n.left, val, sb))
            sb.append("L");
        else if (n.right != null && find(n.right, val, sb))
            sb.append("R");
        return sb.length() > 0;
    }
}

这个思路我只能说我永远也想不出来. 从root到startNode和root到endNode的route我们都能得到. 然后我们要做的是先把二者common prefix去掉, 然后把startNodeRoute剩下的cha都换成U, 也就是这表示startNode先一路向上到common prefix的结尾处, 再加上endNodeRoute删除common prefix的剩下的字符也就是从common prefix处再一路向下到endNode.

时间复杂度: O(n)
空间复杂度: O(n)

这道题还了解了从下而上构建东西的思路.