leetcode-5944:从二叉树一个节点到另一个节点每一步的方向

简介: leetcode-5944:从二叉树一个节点到另一个节点每一步的方向

题目

题目链接

给你一棵 二叉树 的根节点 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 。

解题

方法一:DFS+回溯

  • 先通过深搜找到从根节点分别到两个点的路径字符串
  • 然后将两字符串的相同前缀同时删去
  • 例如两字符串:“LLRR"和"LRL”,将前缀"L"删除,表示从根节点向左走一步,到达两个目标结点的最近父结点
    最后将起始结点对应字符串所剩下的字符全部改成’U’,再拼接终点结点所对应的字符串就是答案了

例子

最后遍历完后 pathS="513" ,pathD="526"

通过这一步 while(pathS[i]==pathD[j]) i++,j++; 使得 pathS[i:]="13",pathD[j:]="26"

然后将35的那一部分变成‘U’,因此可以得到"UURL";

class Solution {
public:
    string path,pathS,pathD;
    void dfs(TreeNode* root,int startValue,int destValue){
        if(!root) return;
        if(root->val==startValue) pathS=path;
        if(root->val==destValue) pathD=path;
        if(root->right) path+='R',dfs(root->right,startValue,destValue),path.pop_back();//回溯
        if(root->left) path+='L',dfs(root->left,startValue,destValue),path.pop_back();//回溯
    }
    string getDirections(TreeNode* root, int startValue, int destValue) {
        dfs(root,startValue,destValue);
        int i=0,j=0;
        while(pathS[i]==pathD[j]) i++,j++;
        return string(pathS.size()-i,'U')+pathD.substr(j);
    }
};


相关文章
|
1月前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
19 2
|
1月前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
15 2
|
1月前
【LeetCode 28】102.二叉树的层序遍历
【LeetCode 28】102.二叉树的层序遍历
15 2
|
1月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
17 0
LeetCode第二十四题(两两交换链表中的节点)
|
1月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
40 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
1月前
【LeetCode 46】450.删除二叉搜索树的节点
【LeetCode 46】450.删除二叉搜索树的节点
15 0
|
1月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
18 0
|
1月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
14 0
|
1月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
16 0
|
1月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
12 0