LeetCode 1372. 二叉树中的最长交错路径

Categories:

题目描述
思路分析
1. 解法一：DFS 返回双方向长度（推荐）
相似题目

题目描述

✅ 1372. 二叉树中的最长交错路径

思路分析

解法一：DFS 返回双方向长度（推荐）

核心思路：

DFS 返回从当前节点出发、上一步向左/向右的最长交错长度。

若从左子树回到父节点，下一步必须向右，长度为 left.right + 1。

全局维护最大值。

复杂度分析：

时间复杂度：O(n)，每个节点访问一次。

空间复杂度：O(h)，递归栈深度。

class Solution {
    private int ans = 0;

    public int longestZigZag(TreeNode root) {
        dfs(root);
        return ans;
    }

    private int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[] {-1, -1};
        }
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);

        int leftLen = left[1] + 1;
        int rightLen = right[0] + 1;

        ans = Math.max(ans, Math.max(leftLen, rightLen));
        return new int[] {leftLen, rightLen};
    }
}

func longestZigZag(root *TreeNode) int {
    ans := 0

    var dfs func(node *TreeNode) (int, int)
    dfs = func(node *TreeNode) (int, int) {
        if node == nil {
            return -1, -1
        }
        l0, l1 := dfs(node.Left)
        r0, r1 := dfs(node.Right)

        leftLen := l1 + 1
        rightLen := r0 + 1
        if leftLen > ans {
            ans = leftLen
        }
        if rightLen > ans {
            ans = rightLen
        }
        return leftLen, rightLen
    }

    dfs(root)
    return ans
}

相似题目

题目	难度	考察点
112. 路径总和	简单	DFS
124. 二叉树中的最大路径和	困难	DFS
687. 最长同值路径	中等	树 DP
543. 二叉树的直径	简单	树 DP
113. 路径总和 II	中等	DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/13922938