Java 1-pass DFS solution 15ms


  • 0
    public class Solution {
        
        int maxPath = 0;
        
        class Result {
            int ld, li, rd, ri; // left/right longest decreasing/increasing length
            public Result(int _ld, int _li, int _rd, int _ri) {
                ld = _ld; li = _li; rd = _rd; ri = _ri;
            }
        }
        
        private Result dfs(TreeNode node) {
            Result res = new Result(0,0,0,0);
            if(node.left!=null) {
                Result leftRes = dfs(node.left);
                if(node.left.val-node.val==1) { // increase
                    res.li = 1+Math.max(leftRes.li, leftRes.ri);
                } else if(node.left.val-node.val==-1) { // decrease
                    res.ld = 1+Math.max(leftRes.ld, leftRes.rd);
                }
            }
            if(node.right!=null) {
                Result rightRes = dfs(node.right);
                if(node.right.val-node.val==1) { // increase
                    res.ri = 1+Math.max(rightRes.li, rightRes.ri);
                } else if(node.right.val-node.val==-1) { // decrease
                    res.rd = 1+Math.max(rightRes.ld, rightRes.rd);
                }
            }
            maxPath = Math.max(maxPath, Math.max(res.ri+res.ld+1, res.li+res.rd+1)); // +1 account for current node
            return res;
        }
        
        public int longestConsecutive(TreeNode root) {
            if(root==null)
                return 0;
            dfs(root);
            return maxPath;
        }
    }

Log in to reply
 

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