上次编辑到这里，代码来自缓存 点击恢复默认模板
/**
* 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 {
public:
string getDirections(TreeNode* root, int startValue, int destValue) {
}
};
java 解法, 执行用时: 33 ms, 内存消耗: 78.5 MB, 提交时间: 2023-10-10 23:28:40
/**
* 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 {
List<List<Character>> lls; //保存第二次和第三次回溯正确路径的集合
List<Character> findStart; //保存第二次找起始节点的正确路径结合
List<Character> findDest; //保存第三次找终点节点的正确路径集合
public String getDirections(TreeNode root, int startValue, int destValue) {
this.lls = new ArrayList<>();
this.findStart = new ArrayList<>();
this.findDest = new ArrayList<>();
//找到两个节点的最近公共祖先节点
TreeNode commonRoot = findRoot(root, startValue, destValue);
//第二次回溯找起始节点的正确路径
dfsStart(commonRoot, startValue);
//第三次回溯找终点节点的正确路径
dfsDest(commonRoot, destValue);
StringBuilder sb = new StringBuilder();
//获取两次回溯正确路径的每一步结果
for(List<Character> paths : lls){
for(char path : paths) sb.append(path);
}
return sb.toString();
}
public TreeNode findRoot(TreeNode root, int startValue, int destValue){
if(root == null || root.val == startValue || root.val == destValue) return root;
TreeNode left = findRoot(root.left, startValue, destValue);
TreeNode right = findRoot(root.right, startValue, destValue);
if(left == null) return right;
if(right == null) return left;
return root;
}
public void dfsStart(TreeNode root, int startValue){
if(root == null) return;
//找到起始节点，保存该正确路径
if(root.val == startValue){
lls.add(new ArrayList<>(findStart));
return;
}
//不管往左子树还是右子树遍历，从起始节点出发都是从下向上前往父节点
findStart.add('U');
dfsStart(root.left, startValue);
findStart.remove(findStart.size()-1);
findStart.add('U');
dfsStart(root.right, startValue);
findStart.remove(findStart.size()-1);
}
public void dfsDest(TreeNode root, int destValue){
if(root == null) return;
//找到终点节点，保存该正确路径
if(root.val == destValue){
lls.add(new ArrayList<>(findDest));
return;
}
//往当前节点的左子树遍历
findDest.add('L');
dfsDest(root.left, destValue);
//回溯
findDest.remove(findDest.size()-1);
//往当前节点的右子树遍历
findDest.add('R');
dfsDest(root.right, destValue);
//回溯
findDest.remove(findDest.size()-1);
}
}
java 解法, 执行用时: 29 ms, 内存消耗: 92.5 MB, 提交时间: 2023-10-10 23:28:18
/**
* 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 {
StringBuilder res = new StringBuilder();
public String getDirections(TreeNode root, int startValue, int destValue) {
StringBuilder sb = new StringBuilder();
TreeNode newRoot = dfs(root, startValue, destValue);
//添加start到root的路径
int num = findSrc(newRoot, startValue);
for(int i = 0; i < num; i++){
res.append('U');
}
//添加root到dest的路径
findDest(newRoot, destValue, sb);
return res.toString();
}
//寻找最近的公共祖先newRoot
public TreeNode dfs(TreeNode root, int startValue, int destValue){
if(root == null || root.val == startValue || root.val == destValue){
return root;
}
TreeNode l = dfs(root.left, startValue, destValue);
TreeNode r = dfs(root.right, startValue, destValue);
if(l != null && r != null){
return root;
}
if(l == null){
return r;
}
if(r == null){
return l;
}
return null;
}
//寻找newRoot到dest的路径
public void findDest(TreeNode root, int destValue, StringBuilder sb){
if(root.val == destValue){
res.append(sb.toString());
return;
}
if(root.right != null){
sb.append('R');
findDest(root.right, destValue, sb);
sb.deleteCharAt(sb.length() - 1);
}
if(root.left != null){
sb.append('L');
findDest(root.left, destValue, sb);
sb.deleteCharAt(sb.length() - 1);
}
}
//寻找start到newRoot有几个U
public int findSrc(TreeNode root, int srcValue){
if(root == null){
return 10000;
}
if(root.val == srcValue){
return 0;
}
return Math.min(findSrc(root.left, srcValue), findSrc(root.right, srcValue)) + 1;
}
}
python3 解法, 执行用时: 612 ms, 内存消耗: 146.6 MB, 提交时间: 2023-10-10 23:27:42
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
fa = {} # 父节点哈希表
s = None # 起点节点
t = None # 终点节点
# 深度优先搜索维护哈希表与起点终点
def dfs(curr: TreeNode) -> None:
nonlocal s, t
if curr.val == startValue:
s = curr
if curr.val == destValue:
t = curr
if curr.left:
fa[curr.left] = curr
dfs(curr.left)
if curr.right:
fa[curr.right] = curr
dfs(curr.right)
dfs(root)
# 求出根节点到对应节点的路径字符串
def path(curr: TreeNode) -> List[str]:
res = []
while curr != root:
par = fa[curr]
if curr == par.left:
res.append('L')
else:
res.append('R')
curr = par
return res[::-1]
path1 = path(s)
path2 = path(t)
# 计算最长公共前缀并删去对应部分，同时将 path_1 逐字符修改为 'U'
l1, l2 = len(path1), len(path2)
i = 0
while i < min(l1, l2):
if path1[i] == path2[i]:
i += 1
else:
break
finalpath = 'U' * (l1 - i) + ''.join(path2[i:]) # 最短路径对应字符串
return finalpath
cpp 解法, 执行用时: 488 ms, 内存消耗: 210.3 MB, 提交时间: 2023-10-10 23:27:16
/**
* 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 {
public:
string getDirections(TreeNode* root, int startValue, int destValue) {
unordered_map<TreeNode*, TreeNode*> fa; // 父节点哈希表
TreeNode* s = nullptr; // 起点节点
TreeNode* t = nullptr; // 终点节点
// 深度优先搜索维护哈希表与起点终点
function<void(TreeNode*)> dfs = [&](TreeNode* curr) {
if (curr->val == startValue) {
s = curr;
}
if (curr->val == destValue) {
t = curr;
}
if (curr->left) {
fa[curr->left] = curr;
dfs(curr->left);
}
if (curr->right) {
fa[curr->right] = curr;
dfs(curr->right);
}
};
dfs(root);
// 求出根节点到对应节点的路径字符串
function<string(TreeNode*)> path = [&](TreeNode* curr) {
string res;
while (curr != root) {
TreeNode* par = fa[curr];
if (curr == par->left) {
res.push_back('L');
}
else {
res.push_back('R');
}
curr = par;
}
reverse(res.begin(), res.end());
return res;
};
string path1 = path(s);
string path2 = path(t);
// 计算最长公共前缀并删去对应部分，同时将 path_1 逐字符修改为 'U'
int l1 = path1.size(), l2 = path2.size();
int i = 0;
while (i < min(l1, l2)) {
if (path1[i] == path2[i]) {
++i;
}
else {
break;
}
}
string finalpath(l1 - i, 'U'); // 最短路径对应字符串
finalpath.append(path2.substr(i, l2 - i));
return finalpath;
}
};
golang 解法, 执行用时: 236 ms, 内存消耗: 57.5 MB, 提交时间: 2023-10-10 23:26:53
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
从起点出发，找到到起点和终点的路径，然后去掉前缀相同的部分。
剩下即为从起点和终点的最近公共祖先出发，到起点和终点的路径，
分别记作 pathToStart 和 pathToDest。
我们要找的最短路径即为：起点 => 起点和终点的最近公共祖先 => 终点。
对于起点到最近公共祖先这一段，可以看成长度为 pathToStart 的向父节点走的路径；
对于最近公共祖先到终点这一段就是 pathToDest。将这两段路径拼起来即为答案。
*/
func getDirections(root *TreeNode, startValue, destValue int) string {
var path []byte
var dfs func(*TreeNode, int) bool
dfs = func(node *TreeNode, target int) bool {
if node == nil {
return false
}
if node.Val == target {
return true
}
path = append(path, 'L')
if dfs(node.Left, target) {
return true
}
path[len(path)-1] = 'R'
if dfs(node.Right, target) {
return true
}
path = path[:len(path)-1]
return false
}
dfs(root, startValue)
pathToStart := path
path = nil
dfs(root, destValue)
pathToDest := path
for len(pathToStart) > 0 && len(pathToDest) > 0 && pathToStart[0] == pathToDest[0] {
pathToStart = pathToStart[1:] // 去掉前缀相同的部分
pathToDest = pathToDest[1:]
}
return strings.Repeat("U", len(pathToStart)) + string(pathToDest)
}
golang 解法, 执行用时: 420 ms, 内存消耗: 38.8 MB, 提交时间: 2023-10-10 23:25:07
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/*
解法一：DFS + BFS
我们可以从起点出发，通过 BFS 找到终点，同时记录每个点的来源节点和方向，
在找到终点后，顺着来源节点往回走，同时记录答案。
由于要往父节点方向走，我们需要先通过一次 DFS 记录每个节点的父节点，
这样就可以在 BFS 中往父节点和左右节点三个方向前进了。
DFS 的过程中也可以顺带找到起点。
*/
func getDirections(root *TreeNode, startValue, destValue int) string {
q := []*TreeNode{nil}
parents := map[*TreeNode]*TreeNode{}
var dfs func(node, pa *TreeNode)
dfs = func(node, pa *TreeNode) {
if node == nil {
return
}
parents[node] = pa
if node.Val == startValue {
q[0] = node // 只有一个起点
}
dfs(node.Left, node)
dfs(node.Right, node)
}
dfs(root, nil)
ans := []byte{}
vis := map[*TreeNode]bool{nil: true, q[0]: true}
type pair struct {
from *TreeNode
dir byte
}
from := map[*TreeNode]pair{}
for len(q) > 0 {
node := q[0]
q = q[1:]
if node.Val == destValue {
for ; from[node].from != nil; node = from[node].from {
ans = append(ans, from[node].dir)
}
break
}
if !vis[node.Left] {
vis[node.Left] = true
from[node.Left] = pair{node, 'L'}
q = append(q, node.Left)
}
if !vis[node.Right] {
vis[node.Right] = true
from[node.Right] = pair{node, 'R'}
q = append(q, node.Right)
}
if !vis[parents[node]] {
vis[parents[node]] = true
from[parents[node]] = pair{node, 'U'}
q = append(q, parents[node])
}
}
for i, n := 0, len(ans); i < n/2; i++ {
ans[i], ans[n-1-i] = ans[n-1-i], ans[i]
}
return string(ans)
}
