step-by-step-directions-from-a-binary-tree-node-to-another

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given the <code>root</code> of a binary tree with <code>n</code> nodes. Each node is uniquely assigned a value from <code>1</code> to <code>n</code>. You are also given an integer <code>startValue</code> representing the value of the start node <code>s</code>, and a different integer <code>destValue</code> representing the value of the destination node <code>t</code>.

Find the shortest path starting from node <code>s</code> and ending at node <code>t</code>. Generate step-by-step directions of such path as a string consisting of only the uppercase letters <code>&#39;L&#39;</code>, <code>&#39;R&#39;</code>, and <code>&#39;U&#39;</code>. Each letter indicates a specific direction:

<ul>
	<li><code>&#39;L&#39;</code> means to go from a node to its left child node.</li>
	<li><code>&#39;R&#39;</code> means to go from a node to its right child node.</li>
	<li><code>&#39;U&#39;</code> means to go from a node to its parent node.</li>
</ul>

Return the step-by-step directions of the shortest path from node <code>s</code> to node <code>t</code>.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/15/eg1.png" style="width: 214px; height: 163px;" />
<pre>
Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
Output: &quot;UURL&quot;
Explanation: The shortest path is: 3 &rarr; 1 &rarr; 5 &rarr; 2 &rarr; 6.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/15/eg2.png" style="width: 74px; height: 102px;" />
<pre>
Input: root = [2,1], startValue = 2, destValue = 1
Output: &quot;L&quot;
Explanation: The shortest path is: 2 &rarr; 1.
</pre>

&nbsp;
Constraints:

<ul>
	<li>The number of nodes in the tree is <code>n</code>.</li>
	<li><code>2 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= Node.val &lt;= n</code></li>
	<li>All the values in the tree are unique.</li>
	<li><code>1 &lt;= startValue, destValue &lt;= n</code></li>
	<li><code>startValue != destValue</code></li>
</ul>

getDirections

Step-By-Step Directions From a Binary Tree Node to Another

Path Sum II

path-sum-ii

路径总和 II

Lowest Common Ancestor of a Binary Tree

lowest-common-ancestor-of-a-binary-tree

二叉树的最近公共祖先

Binary Tree Paths

binary-tree-paths

二叉树的所有路径

Find Distance in a Binary Tree

find-distance-in-a-binary-tree

找到二叉树中的距离

Tree

Depth-First Search

String

Binary Tree

给你一棵 二叉树&nbsp;的根节点&nbsp;<code>root</code>&nbsp;，这棵二叉树总共有&nbsp;<code>n</code>&nbsp;个节点。每个节点的值为&nbsp;<code>1</code>&nbsp;到&nbsp;<code>n</code>&nbsp;中的一个整数，且互不相同。给你一个整数&nbsp;<code>startValue</code>&nbsp;，表示起点节点 <code>s</code>&nbsp;的值，和另一个不同的整数&nbsp;<code>destValue</code>&nbsp;，表示终点节点&nbsp;<code>t</code>&nbsp;的值。

请找到从节点&nbsp;<code>s</code>&nbsp;到节点 <code>t</code>&nbsp;的 最短路径&nbsp;，并以字符串的形式返回每一步的方向。每一步用 大写&nbsp;字母&nbsp;<code>'L'</code>&nbsp;，<code>'R'</code>&nbsp;和&nbsp;<code>'U'</code>&nbsp;分别表示一种方向：

<ul>
	<li><code>'L'</code>&nbsp;表示从一个节点前往它的 左孩子&nbsp;节点。</li>
	<li><code>'R'</code>&nbsp;表示从一个节点前往它的 右孩子&nbsp;节点。</li>
	<li><code>'U'</code>&nbsp;表示从一个节点前往它的 父&nbsp;节点。</li>
</ul>

请你返回从 <code>s</code>&nbsp;到 <code>t</code>&nbsp;最短路径&nbsp;每一步的方向。

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode.com/uploads/2021/11/15/eg1.png" style="width: 214px; height: 163px;">

<pre>输入：root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
输出："UURL"
解释：最短路径为：3 → 1 → 5 → 2 → 6 。
</pre>

示例 2：

<img alt="" src="https://assets.leetcode.com/uploads/2021/11/15/eg2.png" style="width: 74px; height: 102px;">

<pre>输入：root = [2,1], startValue = 2, destValue = 1
输出："L"
解释：最短路径为：2 → 1 。
</pre>

&nbsp;

提示：

<ul>
	<li>树中节点数目为&nbsp;<code>n</code>&nbsp;。</li>
	<li><code>2 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= Node.val &lt;= n</code></li>
	<li>树中所有节点的值 互不相同&nbsp;。</li>
	<li><code>1 &lt;= startValue, destValue &lt;= n</code></li>
	<li><code>startValue != destValue</code></li>
</ul>