做沙盘实训在哪个网站做,成都营销网站制作,上海建设电动车官方网站,无极网页游戏文章目录1. 题目2. 解题1. 题目
给你一棵 二叉树 的根节点 root #xff0c;这棵二叉树总共有 n 个节点。 每个节点的值为 1 到 n 中的一个整数#xff0c;且互不相同。 给你一个整数 startValue #xff0c;表示起点节点 s 的值#xff0c;和另一个不同的整数 destValue …
文章目录1. 题目2. 解题1. 题目
给你一棵 二叉树 的根节点 root 这棵二叉树总共有 n 个节点。 每个节点的值为 1 到 n 中的一个整数且互不相同。 给你一个整数 startValue 表示起点节点 s 的值和另一个不同的整数 destValue 表示终点节点 t 的值。
请找到从节点 s 到节点 t 的 最短路径 并以字符串的形式返回每一步的方向。 每一步用 大写 字母 ‘L’ ‘R’ 和 ‘U’ 分别表示一种方向
L 表示从一个节点前往它的 左孩子 节点。R 表示从一个节点前往它的 右孩子 节点。U 表示从一个节点前往它的 父 节点。
请你返回从 s 到 t 最短路径 每一步的方向。
示例 1
输入root [5,1,2,3,null,6,4],
startValue 3, destValue 6
输出UURL
解释最短路径为3 → 1 → 5 → 2 → 6 。示例 2
输入root [2,1], startValue 2, destValue 1
输出L
解释最短路径为2 → 1 。提示
树中节点数目为 n 。
2 n 10^5
1 Node.val n
树中所有节点的值 互不相同 。
1 startValue, destValue n
startValue ! destValue来源力扣LeetCode 链接https://leetcode-cn.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
先求解两个点的最小公共祖先 p然后 dfs1 求解 p 到 start 的步数 x得到答案有 x 个 U再 dfs2 求解 p 到 end 的路径就是答案的 后半部分
/*** 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), right(right) {}* };*/
class Solution {int stepdowntofindstart -1;bool finddest false;string pathtodest, path;
public:string getDirections(TreeNode* root, int startValue, int destValue) {TreeNode* p lowestcommonParent(root, startValue, destValue);dfs1(p, startValue, 0);dfs2(p, destValue);if(stepdowntofindstart)return string(stepdowntofindstart, U) pathtodest;return pathtodest;}TreeNode* lowestcommonParent(TreeNode* root, int sv, int dv){ // 最小公共祖先if(!root) return root;if(root-val sv || root-val dv)return root;auto l lowestcommonParent(root-left, sv, dv);auto r lowestcommonParent(root-right, sv, dv);if(l r) return root;return l ? l : r;}void dfs1(TreeNode* root, int sv, int step){ // 最小祖先到 start 的步数if(stepdowntofindstart ! -1 || !root) return;if(root-val sv){stepdowntofindstart step;return;}dfs1(root-left, sv, step1);dfs1(root-right, sv, step1);}void dfs2(TreeNode* root, int dv){ // 最小祖先到 end 的路径 pathif(finddest || !root) return;if(root-val dv){finddest true;pathtodest path;return;}path.push_back(L);dfs2(root-left, dv);path.pop_back();path.push_back(R);dfs2(root-right, dv);path.pop_back();}
};164 ms 111.3 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
