※ 引述《oin1104 (是oin的说)》之铭言：
: ※ 引述 《Rushia (早瀬ユウカの体操服)》 之铭言：
: :
: : https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-
: : to-another/
: : 2096. Step-By-Step Directions From a Binary Tree Node to Another
: : 给你一个二元树的根节点以及startValue、destValue，你可以往上、往右、往左移动，
: 求
: : 出startValue到destValue的最短路径要怎么走。
: :
: 思路 :
: 偷看到删除共同路径
: 就知道什么意思了
: 就是有点像前缀合的感觉
: 把走过的一样的路删掉
: 那些都是多余的
: 这样就可以找到最开始不一样的地方
: 那就是最短的路
: 我要去吃早餐了
: ```cpp
: /**
: * Definition for a binary tree node.
: * struct TreeNode {
: * int val;
: * TreeNode *left;
: * TreeNode *right;
: * TreeNode() : val(0), left(nullptr), right(nullptr) {}
: * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
: * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), ri
: ght(right) {}
: * };
: */
: class Solution {
: public:
: string startpath;
: string destpath;
: int startValuea;
: string path;
: void find(TreeNode* root , int target)
: {
: if(root == NULL)return ;
: if(target == root->val)
: {
: if(target == startValuea)
: {
: startpath = path;
: }
: else
: {
: destpath = path;
: }
: return ;
: }
: path+="L";
: find(root->left,target);
: path.pop_back();
: path+="R";
: find(root->right,target);
: path.pop_back();
: }
: string getDirections(TreeNode* root, int startValue, int destValue)
: {
: startValuea = startValue;
: find(root,startValue);
: find(root,destValue);
: int sp = 0;
: int dp = 0;
: while(dp<destpath.size() && sp<startpath.size() && startpath[sp] == dest
: path[dp])
: {
: sp++;
: dp++;
: }
: string res(startpath.size()-sp,'U');
: res += destpath.substr(dp,destpath.size()-dp);
: return res;
: }
: };
: ```
思路:
都是删除共同路径
有相同路径代表没找到LCA
找到LCA再接起来就最短路径
Python Code:
class Solution:
def getDirections(self, root: Optional[TreeNode], startValue: int,
destValue: int) -> str:
def dfs(node, record, goal):
if not node:
return None
if node.val == goal:
return record
if node.left:
record.append([node.left.val, "L"])
result = dfs(node.left, record, goal)
if result is not None:
return result
record.pop()
if node.right:
record.append([node.right.val, "R"])
result = dfs(node.right, record, goal)
if result is not None:
return result
record.pop()
return None
start_record = []
dest_record = []
start = dfs(root, start_record, startValue)
dest = dfs(root, dest_record, destValue)
i = 0
while i < len(start) and i < len(dest):
if start[i][0] == dest[i][0]:
start.pop(i)
dest.pop(i)
else:
break
result = "U" * len(start)
for i in range(len(dest)):
result += dest[i][1]
return result
等等试试拆成图的写法好了
我看LCA高效解都要变成图