tag:blogger.com,1999:blog-4731036105252322780.post242144917081185233..comments2024-03-01T02:55:58.951-08:00Comments on Buttercola: Leetcode: Verify Preorder Sequence in Binary Search Tree Butter is looking for a jobhttp://www.blogger.com/profile/01481083468821703855noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-4731036105252322780.post-18524266814814701922017-04-21T02:42:19.069-07:002017-04-21T02:42:19.069-07:00What about using structure to solve using one stac...What about using structure to solve using one stack?<br /><br />public class BSTPreorderValidator{<br /> <br /> class Segment{<br /> int left, right;<br /><br /> public Segment(int left, int right){<br /> this.left = left;<br /> this.right = right;<br /> }<br /> }<br /><br /> public boolean isValid(int [] preorder){<br /> if(preorder == null || preorder.length == 0) return true;<br /> Stack segmentStack = new Stack<>();<br /> segmentStack.push(new Segment(0, preorder.length-1));<br /> while(!st.isEmpty()){<br /> Segment segment = segmentStack.pop();<br /> if(segment.left > segment.right) continue;<br /> int rootVal = preorder[segment.left];<br /> int mid = segment.left+1;<br /> while(mid <= segment.r && preorder[mid] < rootVal){<br /> mid++;<br /> }<br /> for(int i = mid;i<=segment.r;i++){<br /> if(preorder[i] <= rootVal) return false;<br /> }<br /> st.push(new Segment(0, mid-1));<br /> st.push(new Segment(mid, segment.r));<br /> }<br /> return true;<br /> }<br /><br /> <br /><br />}Anonymoushttps://www.blogger.com/profile/15594073291332747883noreply@blogger.comtag:blogger.com,1999:blog-4731036105252322780.post-55637536487322022482015-12-21T12:38:32.674-08:002015-12-21T12:38:32.674-08:00The space of the first one should be O(logn) as it...The space of the first one should be O(logn) as it is recursion on sub tree.Donaldhttps://www.blogger.com/profile/06360055497248704194noreply@blogger.comtag:blogger.com,1999:blog-4731036105252322780.post-62857370046065432782015-12-21T12:38:05.754-08:002015-12-21T12:38:05.754-08:00The space of the first one should be O(logn) as it...The space of the first one should be O(logn) as it is recursion on sub tree.Donaldhttps://www.blogger.com/profile/06360055497248704194noreply@blogger.comtag:blogger.com,1999:blog-4731036105252322780.post-30725100970136039752015-10-04T10:54:53.244-07:002015-10-04T10:54:53.244-07:00The space complexity of the first method should be...The space complexity of the first method should be O(N)Anonymoushttps://www.blogger.com/profile/05602572208204528569noreply@blogger.com