推 CanIndulgeMe: 技術大神 07/16 16:22
推 oin1104: 大師 07/16 16:26
推 JIWP: 別卷了 07/16 16:26
推 wwndbk: 大師 07/16 16:28
※ 引述《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高效解都要變成圖
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.194.160.111 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1721118124.A.483.html