最长的相同节点值路径 · Longest Univalue Path

［抄题］：

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.

Note: The length of path between two nodes is represented by the number of edges between them.

Example 1:

Input:

Output:

Example 2:

Input:

Output:

[暴力解法]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

因为可以不从root开始，以为要分情况：进行后续计算之后发现可以合并：从头开始肯定比较长，没必要讨论
以为左右两边也要分开讨论：结果求和加一下就行了，还是见得太少

［一句话思路］：

点在线段的dfs上加一，没地方直接加，需要单独写公式

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

Example:

                ...

               /

              4 (res = resl + resr = 3)

  (resl = 2) / \ (resr= 1)

    (l = 1) 4   4 (r = 0)

           /

          4
点数是线段数+1

［一刷］：

DFS是嵌套traverse的过程，不能当作返回值，加深理解一下
DFS求的是左边或右边单独的最大值，不是合集，稍微理解下 res[0]是所有值中的最大，需要比较，理解题目

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

DFS求的是单边最大值

［复杂度］：Time complexity: O(n) Space complexity: O(n)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

【重磅】java传递的是引用而不是数值，所以必须是数组才有用

［关键模板化代码］：

三元运算符把DFS特殊情况、扩展直接写了，头次见

int resl = (root.left != null && root.val == root.left.val) ? l + 1 : 0;

int resr = (root.right != null && root.val == root.right.val) ? r + 1 : 0;

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

class Solution {

    public int longestUnivaluePath(TreeNode root) {

        //corner case

        if (root == null) {

            return 0;

        }

        int[] res = new int[1];

        //dfs

        dfs(root, res);

        //return res[0];

        return res[0];

    }

    public int dfs(TreeNode root, int[] res) {

        //int max = 0;

        int l = (root.left != null) ? dfs(root.left, res) : 0;

        int r = (root.right != null) ? dfs(root.right, res) : 0;

        //if root == root.left, +1

        int resl = (root.left != null && root.val == root.left.val) ? l + 1 : 0;

        int resr = (root.right != null && root.val == root.right.val) ? r + 1 : 0;

        //res[0] is sum

        res[0] = Math.max(res[0], resl + resr);

        //return the bigger one of l, r

        return Math.max(resl, resr);

    }

}

秒客网

最长的相同节点值路径 · Longest Univalue Path

相关文章