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

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 搜索即可~

---