【二叉树】二叉树中的最长交错路径

0x00 题目

给你一棵以 ​​root​​ 为根的二叉树，二叉树中的交错路径定义如下：

选择二叉树中 ​​任意​​​ 节点和一个方向（​​左​​​或者​​右​​​）
如果前进方向为​​​右​​​，那么移动到当前节点的的​​右​​​子节点
否则移动到它的​​​左​​​子节点
改变前进方向：​​​左变右​​​或者​​右变左​​​ 重复第二步和第三步，直到你在树中​​无法​​继续移动
交错路径的长度定义为：
访问过的节点​​数目 - 1​​（单个节点的路径长度为 0 ）

请你返回给定树中最长 交错路径 的长度

0x01 思路

采用​​深度​​​优先遍历的方式
遍历​​​下​​​一个子节点时
是能区分出该节点是​​​左​​​节点，还是​​右​​​节点的
通过为每个节点缓存 ​​​2​​​ 个值
一个左值 ​​​left​​​，表示本节点为​​左节点​​​时，到达所需​​路径数​​​ 一个右值 ​​right​​，表示本节点为​​右节点​​时，到达所需​​路径数​​ 因为节点要么是​​左​​节点，要么是​​右​​节点
所以两个值，必需有一个为 ​​0​​ 另外一个，根据本节点是​​左​​是​​右​​来确定
是​​左​​节点，则使用父节点的​​右值 + 1​​ (rihgt + 1)
是​​右​​节点，则使用父节点的​​左值 + 1​​ (left + 1)
最后使用一个​​全局​​变量
保存最大值即可

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 longestZigZag(_ root: TreeNode?) -> Int {
    var res: Int = 0
    
    func dfs(_ root: TreeNode?, _ left: Int, _ right: Int) {
        // 最大长度
        res = max(res, max(left, right))
        
        // 左子树存在，往右
        if let l = root?.left {
            dfs(l, right+1, 0)
        }
        
        // 右子树存在，往左
        if let r = root?.right {
            dfs(r, 0, left+1)
        }
    }
    
    dfs(root, 0, 0)
    return res
}

0x03 我的小作品

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