“This is the 16th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

[B] [C] [D]

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

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

Example 1:

Input:

5 / \ 4 5 / \ 1 1 5Copy the code

Output:

2
Copy the code

Example 2:

Input:

1 / \ 4 5 / \ 4 4 5Copy the code

Output:

2
Copy the code

Note: A given binary tree has no more than 10,000 nodes. The height of the tree does not exceed 1000.

Their thinking

So this is a naked recursive problem. To find the longest same-valued path, you can find all the same-valued paths, and then find the maximum of them. So how do you get all the same value paths? If we observe the binary tree, we can find that every path has one vertex. If we take every node as the vertex to obtain the same-valued path, we can obtain all the same-valued paths. So we can find the same value path with each node as the vertex through the binary tree of recursive input. So how do we get the same value path? First, in the process of downward recursion, we need to record the parent value of the current node for use in the backtracking process. In the process of backtracking, assuming that we have got the length of the same-valued path of the current node, if the value of the parent node is the same as the value of the current node, then the parent node and the current node can form the same-valued path, we should take the value of the same-valued path of the current node +1 as the return value. +1 is because the parent node has the same value as the current node, and the edge between them is an edge of the path with the same value. If the parent node has a different value than the current node, they cannot form a path with the same value, in which case 0 is returned. The length of the path with the same value of the current node as the vertex is the return value of the left subtree plus the return value of the right subtree. Every time we get the path with the same value of the current node as the vertex, we try to update the result value with this length. In this way, we can obtain the longest path with the same value in the binary tree.

Code implementation

Var longestUnivaluePath = function(root) {// Let Max = 0; Function findPath(node){if(node === null) return 0; if(node === null) return 0; // Record the value of the parent of the current node. ParentVal = node.val if(node.right) node.right. ParentVal = node.val // get the return value of the left subtree const l = findPath(node.left), Max = math.max (Max,l+r) // If there is a parent node, the node value is the same as the current node value // If (node.parentVal===node.val) return math.max (l,r)+1 // If (node.parentval === Node.val) return math.max (l,r)+1 } // call method findPath(root) // return result value return Max; };Copy the code

At this point we are done with Leetcode-687 – the longest iden-valued path

If you have any questions or suggestions, please leave a comment! 👏 🏻 👏 🏻 👏 🏻