提问:一道DFS类型题目

是lintcode上的一道题,核心算法是深度优先搜索

原题地址

题干描述:

给定一颗二叉树,找到路径中每个节点具有相同值的最长路径的长度。 此路径可能会也可能不会通过根节点。

提示:

  1. 两个节点之间的路径长度由它们之间的边数表示。

  2. 给定的二叉树不超过10000个节点。 树的高度不超过1000。

然后我是发现 @Bo0lean 大佬的题解,他的算法我看得朦朦胧胧不算太懂,想问问有没有人可以帮我详细解释一下,或者有更好的算法也可以提出(最好解释一下,萌新太笨了)

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: 
     * @return: the length of the longest path where each node in the path has the same value
     */
    int res = 0;
    public int longestUnivaluePath(TreeNode root) {
        // Write your code here
        if(root == null) {
            return 0;
        }
        help(root);
        return res;
    }
    public void help(TreeNode root) {
        if(root == null) {
            return;
        }
        int temp = count(root.left, root.val) + count(root.right, root.val);
        res = Math.max(res, temp);
        help(root.left);
        help(root.right);
    }
    public int count(TreeNode root, int val) {
        if(root == null || root.val != val) {
            return 0;
        }
        int left = count(root.left, val) + 1;
        int right = count(root.right, val) + 1;
        return Math.max(left, right); 
    }
}
Comments
登录后评论
Sign In
·

我来加一些注释:

  • help:计算以输入参数 root 为根节点的子树在 root 处的最大长度,同时遍历 root 的左子树和右子树,以此得到以 root 为根节点的子树中所有结点处的最大长度
  • count:计算以输入参数 root 为根节点的子树在 root 为路径终点的所有路径中最大的长度,左侧和右侧分别计算,并返回最大值