Daily LeetCode – day0035 0687. Longest Univalue Path

// 0687. Longest Univalue Path
class Solution {
    public int longestUnivaluePath(TreeNode root) {
        int[] ans = new int[]{0};
        if (root == null) return 0;
        dfs(root, ans);
        return ans[0];
    }

    int dfs(TreeNode root, int[] ans) {
        if (root.left == null && root.right == null) return 1;
        int left = 0;
        int right = 0;
        if (root.left != null) {
            left = dfs(root.left, ans);
            if (root.left.val != root.val) left = 0;
        }
        if (root.right != null) {
            right = dfs(root.right, ans);
            if (root.right.val != root.val) right = 0;
        }
        int selfMax = left + right;
        if (selfMax > ans[0]) ans[0] = selfMax;
        if (left > right) return left + 1;
        return right + 1;
    }
}
学习笔记:
今天这道题目之前教学过,这道二叉树题有点像动态规划,需要从下往上状态转移,但由于存储方式是二叉树,所以还是应该用回溯算法,不断递归下去回溯上来。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。