Re: [閒聊] 每日leetcode

[dont (dont)]

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

## 思路

先找兩個node的LCA, 再產生LCA到兩點的路徑

## Complexity

Time, Space: O(N)

## Code

```python
class Solution:
    def getDirections(self, root: Optional[TreeNode], startValue: int,
destValue: int) -> str:

        def find_lca(root, p, q):
            if not root:
                return None
            if root.val == p or root.val == q:
                return root
            left = find_lca(root.left, p, q)
            right = find_lca(root.right, p, q)
            if left and right:
                return root
            return left or right

        def get_path(root, p, path):
            if not root:
                return False
            if root.val == p:
                return True

            path.append('L')
            if get_path(root.left, p, path):
                return True
            path.pop()

            path.append('R')
            if get_path(root.right, p, path):
                return True
            path.pop()

            return False

        lca = find_lca(root, startValue, destValue)

        res = []
        get_path(lca, startValue, res)
        res = ['U' for _ in range(len(res))]
        get_path(lca, destValue, res)
        return ''.join(res)
```

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1721092714.A.789.html
推 DJYOMIYAHINA: 一大早的 放過我
推 sustainer123: 放過我
推 argorok: 大師