【二叉树】从二叉树一个节点到另一个节点每一步的方向

0x00 题目

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

请找到从节点 s 到节点 t 的 最短路径
并以字符串的形式返回每一步的方向
每一步用 大写 字母 ‘L’ ，‘R’ 和 ‘U’ 分别表示一种方向：

L 表示从一个节点前往它的 左孩子 节点
R 表示从一个节点前往它的 右孩子 节点
U 表示从一个节点前往它的 父 节点
请你返回从 s 到 t 最短路径 每一步的方向

---

0x01 思路

因为有 2 个目标
所以有 2 条路径
先把 2 条路径找出来
然后再找出最近的公共祖先
最后再拼接路径

---

0x02 解法

语言：Swift

树节点：TreeNode

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

解法：

func getDirections(_ root: TreeNode?, _ startValue: Int, _ destValue: Int) -> String {
    guard let root = root else { return "" }
    // 第一条路径
    var path1: [(TreeNode, String)] = []
    // 第二条路径
    var path2: [(TreeNode, String)] = []
    // 结果 
    var res = ""
    // 节点和方向
    var arr: [(TreeNode, String)] = []
    
    func dfs(_ root: TreeNode?, _ val: Int, _ type: String) {
        guard let root = root else { return }
        
        // 添加
        arr.append((root, type))
        if root.val == val {
            if val == startValue {
                path1 = Array(arr)
            }else if val == destValue {
                path2 = Array(arr)
            }
            return
        }
        
        dfs(root.left, val, "L")
        dfs(root.right, val, "R")
        // 往回走了，删除最后一个
        arr.removeLast()
    }
    
    // 查找第一条路径
    dfs(root, startValue, "")
    arr.removeAll()
    // 查找第二条路径
    dfs(root, destValue, "")

    var idx1 = 0
    var idx2 = 0
    let idx = min(path1.count, path2.count)
    
    // 去掉路径中相同的前缀
    while idx1 < idx && idx2 < idx {
        let t1 = path1[idx1]
        let t2 = path2[idx2]
        
        if t1.0.val == t2.0.val {
            idx1 += 1
            idx2 += 1
        }else{
            break
        }
    }
    
    // 第一条路径是从下往上走，所以把方向全部调整为 `U`
    for _ in idx1..<path1.count {
        res += "U"
    }
    // 拼接第二条路径
    for i in idx2..<path2.count {
        res += path2[i].1
    }
    
    return res
}

---

0x03 我的小作品

欢迎体验我的作品之一：小五笔 86 版
五笔学习好帮手~
App Store 搜索即可~

---