Added on Feb. 2019
The idea to solve the problem is to avoid using root node to compare with left and right child, two user cases; Every node works with its parent node instead.
It is very challenge to explain and prove the code written is correct based on counting the edge from node to it's parent node.
What I like to suggest is to go over a few steps based on an example to test manually before writing the code. First step is to number every node in the tree using a, b, c, d,..; And then work on edge value calculation following the order of nodes in traversal, specify each edge using node id; third step is to calculate cross path and explain how it works for the maximum value.
I like to show the steps to work on an example, how to explain the idea and come out the design. Since there are so many ways to approach the problems, it is important to make the approach easy to understand.
Added on June 2019
Case study a binary tree
To understand the approach, let us work on simple test case, a binary tree with three nodes, root node with value 5, and left and right child both with value 5 as well:
Here is the overview to display, after that, I will go over one step a time.
Here are hightlights:
- Traversal the tree using post order traversal, mark with a, b, c in the order of traversal for each node;
- Add edge value to each node, every node will check its parent and see its value equal to parent value;
- Add cross path value next to the node from 5a, 5b, 5c. Only 5c has cross path value 2.
Quick overview for each step
Three steps, each step is illustrated one diagram:
step 1: Post order traversal the tree, mark the order using a, b, c next to the node.
step 2: Calculate edge value, and add value next to the node.
step 3: Calculate the cross path value, add value next to the node
The following tree with node value 5 is very helpful to illustrate the process.
The longest univalue path is 2, and the edge count is 2, including one edge from root node to its left child, and one edge from root node to its right child.
There are so many ways to approach the problem, to check with parent value is different from the above counting. The edge is counted from left child to it's parent, likewise the right child to its parent. The node is counting the edges toward itself from direct children nodes first, and also includes it's child's count if need.
How to approach the problem in detail?
A few steps will be explained in the following. using postorder traversal
First, we work on recursive function. Every node is to check with its parent node's path value. Post order traversal, bottom up, three steps, left child 5a, right child 5b, root node 5c, all nodes in the tree have value 5, using a, b c to mark them with unique id, and also alphabetic order is the order of post order traversal.
step 1:
The first node visited is 5a, and its value is equal to it's parent node 5c. 1 edge is added next to 5a. The edge is from node 5a to node 5c.
step 2:
The second node visted is 5b, and its value is equal to it's parent node 5c. One edge is added next to 5b.
step 3:
The third visited node is 5c, and the value does not equal to it's parent node's value. 0 is added next to 5c.
Combination of step 1, 2, 3:
The above tree left child with node value 5, 1 counts for the edge of the node 5 to its parent, in other words, edge from node 5a to 5c;
likewise the right child.
Now the calucation of cross path, bottom up, post order, in the order of 5a, 5b, 5c
Step 1: work on 5a-1-?, cross path value
Step 2: work on 5b-1
Step 3: work on 5c-1
Cross path should be two edges, 5a->5c, 5b->5c
The node 5c's cross path value is 2, since two edges, one is 5a to 5c, and the other is 5b to 5c.
I think that it is definitely good idea in general to go over an example first, and then write the code based on the idea to check with parent value.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace longest_univalue_path___compare_to_root
{
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
class Program
{
static void Main(string[] args)
{
}
int maxCrossPath = 0;
public int LongestUnivaluePath(TreeNode root)
{
if (root == null)
{
return 0;
}
maxCrossPath = 0;
postOrderTraversal(root, root.val);
return maxCrossPath;
}
private int postOrderTraversal(TreeNode node, int parentValue)
{
if (node == null)
{
return 0;
}
var current = node.val;
int left = postOrderTraversal(node.left, current);
int right = postOrderTraversal(node.right, current);
maxCrossPath = Math.Max(maxCrossPath, left + right);
if (parentValue == node.val)
{
return Math.Max(left, right) + 1;
}
return 0;
}
}
}
