Medium

题目描述

给定一个二叉树的根节点 root，返回最长的路径的长度，这个路径中的每个节点具有相同值。这个路径可以经过也可以不经过根节点。

注意：两个节点之间的路径长度由它们之间的边数表示。

示例 1：

输入：root = [5,4,5,1,1,null,5]
输出：2
解释：最长的同值路径如图所示。

示例 2：

输入：root = [1,4,5,4,4,null,5]
输出：2
解释：最长的同值路径如图所示。

提示：

  • 树中节点数的范围是 [0, 10^4]
  • -1000 <= Node.val <= 1000
  • 树的深度不会超过 1000

解题思路

解题思路

这道题要求找到二叉树中最长的同值路径。关键点在于理解路径的定义：路径是由边连接的节点序列，且路径中的所有节点都必须具有相同的值。

核心思想： 使用深度优先搜索(DFS)，对于每个节点，我们需要考虑两种情况：

  1. 经过当前节点的最长同值路径
  2. 从当前节点开始向下延伸的最长同值路径

算法步骤：

  1. 定义一个全局变量记录最长路径长度
  2. 对每个节点，递归计算左右子树中从该节点开始的最长同值路径
  3. 如果当前节点与子节点值相同，则可以延伸路径
  4. 更新全局最大值：考虑经过当前节点连接左右子树的路径
  5. 返回从当前节点开始向下的最长单侧路径长度

推荐解法： DFS + 递归，时间复杂度O(n)，空间复杂度O(h)，其中h是树的高度。

代码实现

class Solution {
public:
    int maxPath = 0;
    
    int longestUnivaluePath(TreeNode* root) {
        if (!root) return 0;
        dfs(root);
        return maxPath;
    }
    
private:
    int dfs(TreeNode* node) {
        if (!node) return 0;
        
        int left = dfs(node->left);
        int right = dfs(node->right);
        
        int leftPath = 0, rightPath = 0;
        
        if (node->left && node->left->val == node->val) {
            leftPath = left + 1;
        }
        if (node->right && node->right->val == node->val) {
            rightPath = right + 1;
        }
        
        maxPath = max(maxPath, leftPath + rightPath);
        
        return max(leftPath, rightPath);
    }
};

class Solution:
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        self.max_path = 0
        
        def dfs(node):
            if not node:
                return 0
            
            left = dfs(node.left)
            right = dfs(node.right)
            
            left_path = right_path = 0
            
            if node.left and node.left.val == node.val:
                left_path = left + 1
            if node.right and node.right.val == node.val:
                right_path = right + 1
            
            self.max_path = max(self.max_path, left_path + right_path)
            
            return max(left_path, right_path)
        
        if not root:
            return 0
        dfs(root)
        return self.max_path

public class Solution {
    private int maxPath = 0;
    
    public int LongestUnivaluePath(TreeNode root) {
        if (root == null) return 0;
        DFS(root);
        return maxPath;
    }
    
    private int DFS(TreeNode node) {
        if (node == null) return 0;
        
        int left = DFS(node.left);
        int right = DFS(node.right);
        
        int leftPath = 0, rightPath = 0;
        
        if (node.left != null && node.left.val == node.val) {
            leftPath = left + 1;
        }
        if (node.right != null && node.right.val == node.val) {
            rightPath = right + 1;
        }
        
        maxPath = Math.Max(maxPath, leftPath + rightPath);
        
        return Math.Max(leftPath, rightPath);
    }
}

var longestUnivaluePath = function(root) {
    let maxPath = 0;
    
    function dfs(node) {
        if (!node) return 0;
        
        let left = dfs(node.left);
        let right = dfs(node.right);
        
        let leftPath = 0, rightPath = 0;
        
        if (node.left && node.left.val === node.val) {
            leftPath = left + 1;
        }
        
        if (node.right && node.right.val === node.val) {
            rightPath = right + 1;
        }
        
        maxPath = Math.max(maxPath, leftPath + rightPath);
        
        return Math.max(leftPath, rightPath);
    }
    
    dfs(root);
    return maxPath;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历二叉树的每个节点一次，其中n是节点总数
空间复杂度O(h)递归调用栈的深度，其中h是树的高度。最坏情况下h=n（退化为链表），平均情况下h=log(n)

相关题目