2096. Step-By-Step Directions From a Binary Tree Node to Another
Step1. Find LCA Step2. Find path LCA->startValue, LCA->destValue Step3. Form return path
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private List<String> paths = new ArrayList<>();
public String getDirections(TreeNode root, int startValue, int destValue) {
TreeNode LCA = getLCA(root, startValue, destValue);
StringBuilder LCAtoStart = new StringBuilder();
StringBuilder LCAtoDest = new StringBuilder();
find(LCA, startValue, LCAtoStart);
find(LCA, destValue, LCAtoDest);
StringBuilder direction = new StringBuilder();
for (char c : paths.get(0).toCharArray()) {
direction.append("U");
}
for (char c : paths.get(1).toCharArray()) {
direction.append(c);
}
return direction.toString();
}
private void find(TreeNode root, int value, StringBuilder sb) {
if (root == null) {
return;
}
if (root.val == value) {
paths.add(sb.toString());
return;
}
if (root.left != null) {
find(root.left, value, sb.append("L"));
}
if (root.right != null) {
find(root.right, value, sb.append("R"));
}
sb.deleteCharAt(sb.length() - 1);
return;
}
private TreeNode getLCA(TreeNode root, int startValue, int destValue) {
if (root == null) {
return null;
}
if (root.val == startValue || root.val == destValue) {
return root;
}
TreeNode left = getLCA(root.left, startValue, destValue);
TreeNode right = getLCA(root.right, startValue, destValue);
if (left != null && right != null) {
return root;
} else {
return left == null ? right : left;
}
}
}