# An iterative solution

• ``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
private void pushLeft(Stack<TreeNode> stack, TreeNode node, Stack<int[]> meta) {
while (node != null) {
stack.push(node);
meta.push(new int[]{1, 1});
node = node.left;
}
}

public int longestUnivaluePath(TreeNode root) {
if (root == null) {
return 0;
}

Stack<TreeNode> stack = new Stack<>();
Stack<int[]> meta = new Stack<>();
pushLeft(stack, root, meta);
int max = 0;
TreeNode pre = null;
int[] preRes = new int[2];
while (!stack.isEmpty()) {
TreeNode node = stack.peek();
int[] m = meta.peek();
m[0] = Math.max(m[0], pre != null && pre.val == node.val ? m[0] + preRes[1] : 1);
m[1] = Math.max(m[1], pre != null && pre.val == node.val ? 1 + preRes[1] : 1);
if (node.right != null && node.right != pre) {
pushLeft(stack, node.right, meta);
preRes = new int[2];
continue;
}
pre = stack.pop();
preRes = meta.pop();
max = Math.max(max, m[0]);
}
return max - 1;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.