LeetCode 687. 最长同值路径

Categories:

题目描述
思路分析
1. 解法一：DFS 计算向下最长同值路径（推荐）
相似题目

题目描述

✅ 687. 最长同值路径

思路分析

解法一：DFS 计算向下最长同值路径（推荐）

核心思路：

递归返回从当前节点向下的最长同值路径长度。

若子节点值等于当前值，则可延伸长度。

用全局变量更新 left + right 作为答案候选。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数。

空间复杂度：O(h)，其中 h 为树高。

class Solution {
    private int ans = 0;

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

    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int left = dfs(node.left);
        int right = dfs(node.right);

        int leftPath = 0;
        int 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;
        }

        ans = Math.max(ans, leftPath + rightPath);
        return Math.max(leftPath, rightPath);
    }
}

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

	var dfs func(node *TreeNode) int
	dfs = func(node *TreeNode) int {
		if node == nil {
			return 0
		}

		left := dfs(node.Left)
		right := dfs(node.Right)

		leftPath := 0
		rightPath := 0
		if node.Left != nil && node.Left.Val == node.Val {
			leftPath = left + 1
		}
		if node.Right != nil && node.Right.Val == node.Val {
			rightPath = right + 1
		}

		if leftPath+rightPath > ans {
			ans = leftPath + rightPath
		}
		if leftPath > rightPath {
			return leftPath
		}
		return rightPath
	}

	dfs(root)
	return ans
}

相似题目

题目	难度	考察点
687. 最长同值路径	中等	DFS
543. 二叉树的直径	简单	DFS
124. 二叉树中的最大路径和	困难	DFS
298. 二叉树最长连续序列	中等	DFS
1026. 节点与其祖先之间的最大差值	中等	DFS
687. 最长同值路径	中等	DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/34199933