[LeetCode] 687. Longest Univalue Path

轉自LeetCode

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:

              5
             / \
            4   5
           / \   \
          1   1   5

Output:

2

Example 2:

Input:

              1
             / \
            4   5
           / \   \
          4   4   5

Output:

2

Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.

<Solution>

想法如下

• 利用 recursive 去計算每個 node 的最大 path 數，過程中並紀錄 global max 是多少

• 先用 recursive 去計算左右子樹的path各是多少，然後檢查當前的 node 和它的子節點的數值是不是一樣，是的話其 path 再加 1，也就是當前的 node 和它的子節點的這個 path

• 每個 recursive 回傳的是當前節點的最大 path 值

code 如下

Java

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	private int ans = 0;
	public int longestUnivaluePath(TreeNode root) {
	calPath(root);
	return ans;
	}
	private int calPath(TreeNode root) {
	if(root == null) {
	return 0;
	}
	int left = calPath(root.left);
	int right = calPath(root.right);
	int leftPathCnt = 0;
	if(root.left != null && root.val == root.left.val) {
	leftPathCnt = 1 + left;
	}
	int rightPathCnt = 0;
	if(root.right != null && root.val == root.right.val) {
	rightPathCnt = 1 + right;
	}
	ans = Math.max(ans, leftPathCnt+rightPathCnt);
	return Math.max(leftPathCnt, rightPathCnt);
	}
	}

view raw longestUnivaluePath.java hosted with ❤ by GitHub

kotlin

	/**
	* Example:
	* var ti = TreeNode(5)
	* var v = ti.`val`
	* Definition for a binary tree node.
	* class TreeNode(var `val`: Int) {
	* var left: TreeNode? = null
	* var right: TreeNode? = null
	* }
	*/
	class Solution {
	var ans = 0
	fun longestUnivaluePath(root: TreeNode?): Int {
	dfs(root)
	return ans
	}
	fun dfs(node: TreeNode?): Int {
	if (node == null) {
	return 0
	}
	val leftResult = dfs(node!!.left)
	val rightResult = dfs(node!!.right)
	var leftCount = 0
	if(node!!.left != null && node!!.left!!.`val` == node!!.`val`) {
	leftCount = 1 + leftResult
	}
	var rightCount = 0
	if(node!!.right != null && node!!.right!!.`val` == node!!.`val`) {
	rightCount = 1 + rightResult
	}
	ans = Math.max(ans, leftCount+rightCount)
	return Math.max(leftCount, rightCount)
	}
	}

view raw longest_univalue_path.kt hosted with ❤ by GitHub