[!info] related notes 算法面试题型 MOC 二叉树高频题

二叉树中的最长交错路径

题目

1372. 二叉树中的最长交错路径 - 力扣（LeetCode）

这里的路径沿父到子方向、左右交替，可从任意节点开始，长度按边数计；单节点为 0。它不同于 锯齿形层序遍历 的输出顺序。

题解

链表-二叉树-回溯

var longestZigZag = function(root) {
    let res = 0;
    // left/right 是到达当前节点、最后一条边分别向左/右的路径长度
    function dfs(node, left, right) {
        if (!node) return 
        res = Math.max(res, left, right);
        dfs(node.left, right + 1, 0);
        dfs(node.right, 0, left + 1);
    }
    dfs(root,0, 0);
    return res;
};

向左孩子延长 right + 1，向右孩子延长 left + 1；重置另一状态为 0，使后续可以从新节点重新开始。时间 O(n)，递归栈 O(h)。