1372. Longest ZigZag Path in a Binary Tree

Leetcode link

题目简介

/**
 * @param {TreeNode} root
 * @return {number}
 */

题目给我们一个二叉树的根节点 root

要求我们计算出这棵树最长的交互路径是多少

交互路径指的是我们沿着二叉树任意节点，走左节点、右节点、左节点……直到遇到 null

路径的长度指的是路径上节点个数 - 1

最后返回最长的路径长度

解题思路

要求树的路径长度（深度）第一反应就是 DFS

这题算是 DFS 的变体，在 DFS 的过程中，我们需要额外记录两个信息：

1. 当前遍历的方向（左还是右） goLeft
2. 当前满足交互路径的长度 len

此外，在 DFS 过程中我们需要考虑两种情况：

1. 我们继续沿着交互的方式走（当前是左接下来走右；反之亦然）
2. 我们重新开始，沿着不交互的方式走（当前是左接下来继续往左；反之亦然）

这两种情况加上当前走的方向，我们可以总结出 4 种走法

最后，我们需要一个全局的 res 来保存最长的结果，并且在每次遍历新节点的时候更新它的值

Javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var longestZigZag = function (root) {
    let res = 0

    // goLeft means next direction
    const dfs = (node, goLeft, len) => {
        if (!node) {
            return
        }

        res = Math.max(len, res)

        if (goLeft) {
            // we go left now, so the next dirextion should be right
            dfs(node.left, false, len + 1)
            // since we don't go left, this node should be the first node
            dfs(node.right, true, 1)
        } else {
            dfs(node.right, true, len + 1)
            dfs(node.left, false, 1)
        }
    }

    // assume we first go right
    dfs(root.right, true, 1)
    // assume we first go left
    dfs(root.left, false, 1)

    return res
};

复杂度分析

假设树的节点数量为 n

时间

我们需要遍历树的每个节点两次，所以是 O(n)

空间

由于是迭代方式遍历树，复杂度取决于树的高度，平均情况为 O(log n)，最差的情况为 O(n)