526互联

2096. 从二叉树一个节点到另一个节点每一步的方向

发布时间 2023-04-03 16:35:06作者: zhangk1988

题目描述

给了一个二叉树，树上所有节点的值不同
再给了两个点的值表示起点和终点，问从起点到终点的最短路的方向？

f1 dfs预处理+最近公共祖先

基本分析

  1. 没有给出起点和终点是哪个点，怎么拿到？一次从root的dfs
  2. s到e的最短路径是哪一条？从公共祖先分别下来的
  3. 怎么从s和e求到公共祖先的path？分别求出从s到root的路径p1和e到root的路径p2，枚举找到第一个不相同的点就是公共祖先
  4. 树中只给了向下的遍历方向，怎么能从节点找到父节点？定义map，从root开始进行一次dfs（可以和1合并）
  5. 自顶向下找path的复杂度是多少，怎么解决？是O(n^2)的，解决办法是从下往上生成path
  6. 拿到p1和p2以后，怎么得到答案？（1）从上到下找到公共的长度;(2)从p1和p2中构造出path

代码

class Solution:
    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
        fa = {}
        s, e = None, None

        # 找到节点对应的父节点，同时找出s和e点
        def dfs(cur):
            nonlocal s, e
            if cur.val == startValue:
                s = cur
            if cur.val == destValue:
                e = cur
            if cur.left:
                fa[cur.left] = cur
                dfs(cur.left)
            if cur.right:
                fa[cur.right] = cur
                dfs(cur.right)
        
        def getpath(cur):
            ans = []
            while cur != root:
                par = fa[cur]
                if cur == par.left:
                    ans.append('L')
                else:
                    ans.append("R")
                cur = par
            return ans[::-1]
        
        dfs(root)
        p1 = getpath(s)
        p2 = getpath(e)

        l1, l2 = len(p1), len(p2)
        i = 0
        while i < min(l1, l2):
            if p1[i] == p2[i]:
                i += 1
            else:
                break
        path = "U" * (l1 - i) + "".join(p2[i:])

        return path

总结

  1. 需要在树上向上遍历时，需要知道节点的父节点是谁？可以通过dfs一次预处理出来
  2. 对于找路径的问题，从上往下的复杂度高，需要考虑自底向上
f2 dfs预处理+bfs
待完善