Medium

题目描述

给你一棵二叉树的根节点 root ，二叉树中节点的值为 1 到 100 。

定义二叉树中的一条交错路径如下：

  • 选择二叉树中 任意 节点和一个方向（左或者右）。
  • 如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
  • 改变前进方向：左变右或者右变左。
  • 重复第二步和第三步，直到你在树中无法继续移动。

交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。

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

示例 1：

输入：root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]
输出：3
解释：蓝色节点为树中最长交错路径（右 -> 左 -> 右）。

示例 2：

输入：root = [1,1,1,null,1,null,null,1,1,null,1]
输出：4
解释：蓝色节点为树中最长交错路径（左 -> 右 -> 左 -> 右）。

示例 3：

输入：root = [1]
输出：0

提示：

  • 树中节点数目在范围 [1, 5 * 10^4] 内
  • 1 <= Node.val <= 100

解题思路

这道题需要找到二叉树中最长的交错路径。交错路径的特点是方向必须交替变换：左→右→左或右→左→右。

解题思路

方法一：深度优先搜索 + 状态记录（推荐）

核心思想是对于每个节点，我们需要记录以该节点为终点的最长交错路径长度，分别考虑从左侧和右侧到达该节点的情况。

对于每个节点，我们维护两个状态：

  1. leftMax：以当前节点为终点，最后一步是从左子节点到达的最长交错路径长度
  2. rightMax：以当前节点为终点，最后一步是从右子节点到达的最长交错路径长度

状态转移：

  • 如果从左子节点到达当前节点，那么前一步必须是向右的，所以 leftMax = rightMax of left child + 1
  • 如果从右子节点到达当前节点，那么前一步必须是向左的，所以 rightMax = leftMax of right child + 1

方法二：直接DFS递归

另一种思路是直接递归，对每个节点分别计算向左和向右开始的最长交错路径，然后取最大值。这种方法更直观但效率稍低。

我们采用方法一，因为它避免了重复计算，时间复杂度更优。

代码实现

class Solution {
public:
    int result = 0;
    
    pair<int, int> dfs(TreeNode* node) {
        if (!node) return {-1, -1};
        
        auto left = dfs(node->left);
        auto right = dfs(node->right);
        
        int leftMax = left.second + 1;   // 从左子节点来，上一步是右
        int rightMax = right.first + 1;  // 从右子节点来，上一步是左
        
        result = max(result, max(leftMax, rightMax));
        
        return {leftMax, rightMax};
    }
    
    int longestZigZag(TreeNode* root) {
        dfs(root);
        return result;
    }
};

class Solution:
    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        self.result = 0
        
        def dfs(node):
            if not node:
                return -1, -1
            
            left_left, left_right = dfs(node.left)
            right_left, right_right = dfs(node.right)
            
            left_max = left_right + 1   # 从左子节点来，上一步是右
            right_max = right_left + 1  # 从右子节点来，上一步是左
            
            self.result = max(self.result, left_max, right_max)
            
            return left_max, right_max
        
        dfs(root)
        return self.result

public class Solution {
    private int result = 0;
    
    private (int, int) Dfs(TreeNode node) {
        if (node == null) return (-1, -1);
        
        var left = Dfs(node.left);
        var right = Dfs(node.right);
        
        int leftMax = left.Item2 + 1;   // 从左子节点来，上一步是右
        int rightMax = right.Item1 + 1; // 从右子节点来，上一步是左
        
        result = Math.Max(result, Math.Max(leftMax, rightMax));
        
        return (leftMax, rightMax);
    }
    
    public int LongestZigZag(TreeNode root) {
        Dfs(root);
        return result;
    }
}

var longestZigZag = function(root) {
    let result = 0;
    
    function dfs(node) {
        if (!node) return [-1, -1];
        
        const [leftLeft, leftRight] = dfs(node.left);
        const [rightLeft, rightRight] = dfs(node.right);
        
        const leftMax = leftRight + 1;   // 从左子节点来，上一步是右
        const rightMax = rightLeft + 1;  // 从右子节点来，上一步是左
        
        result = Math.max(result, leftMax, rightMax);
        
        return [leftMax, rightMax];
    }
    
    dfs(root);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(h)

其中 n 是树中节点的数量，h 是树的高度。时间复杂度为 O(n) 是因为每个节点只被访问一次。空间复杂度为 O(h) 是递归调用栈的深度，最坏情况下为 O(n)（退化为链表）。

相关题目