2 Stack(Totally the same with how OS deal with dfs) Solution


  • 0
    S
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public int longestConsecutive(TreeNode root) {
            Stack<TreeNode> ns = new Stack<TreeNode>();
            Stack<Integer> ls = new Stack<Integer>();
            if (root == null)
                return 0;
            int ans = 0;
            TreeNode curNode = root;
            int curLen = 1;
            while (curNode != null || !ns.isEmpty())
            {
                ans = Math.max(ans, curLen);
                while (curNode != null)
                {
                    ns.push(curNode);
                    ls.push(new Integer(curLen));
                    if (curNode.left == null)
                    {
                        curNode = curNode.left;
                        continue;
                    }
                    if (curNode.left.val == curNode.val + 1)
                    {
                        curLen = curLen + 1;
                    } else {
                        curLen = 1;
                    }
                    curNode = curNode.left;
                    ans = Math.max(ans, curLen);
                }
                if (! ns.isEmpty())
                {
                    curNode = ns.pop();
                    curLen = ls.pop();
                    if (curNode.right == null)
                    {
                        curNode = curNode.right;
                        continue;
                    } else {                    
                        if (curNode.right.val == curNode.val + 1)
                        {
                            curLen = curLen + 1;
                        }
                        else
                            curLen = 1;
                        curNode = curNode.right;
                    }
                }
                
            }
            return ans;
        }
    }
    

Log in to reply
 

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