An iterative solution


  • 0
    M
    /**
     * 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;
        }
    }
    

Log in to reply
 

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