Simple Python solution using stack. With Explanation.


  • 33
    H

    This is very simple problem if you use stacks. The key here is, when you see two consecutive "#" characters on stack, pop both of them and replace the topmost element on the stack with "#". For example,

    preorder = 1,2,3,#,#,#,#

    Pass 1: stack = [1]

    Pass 2: stack = [1,2]

    Pass 3: stack = [1,2,3]

    Pass 4: stack = [1,2,3,#]

    Pass 5: stack = [1,2,3,#,#] -> two #s on top so pop them and replace top with #. -> stack = [1,2,#]

    Pass 6: stack = [1,2,#,#] -> two #s on top so pop them and replace top with #. -> stack = [1,#]

    Pass 7: stack = [1,#,#] -> two #s on top so pop them and replace top with #. -> stack = [#]

    If there is only one # on stack at the end of the string then return True else return False.

    Here is the code for that,

    class Solution(object):
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        stack = []
        top = -1
        preorder = preorder.split(',')
        for s in preorder:
            stack.append(s)
            top += 1
            while(self.endsWithTwoHashes(stack,top)):
                h = stack.pop()
                top -= 1
                h = stack.pop()
                top -= 1
                if top < 0:
                    return False
                h = stack.pop()
                stack.append('#')
            #print stack
        if len(stack) == 1:
            if stack[0] == '#':
                return True
        return False
    
    def endsWithTwoHashes(self,stack,top):
        if top<1:
            return False
        if stack[top]=='#' and stack[top-1]=='#':
            return True
        return False

  • 0
    E

    Nice thinking!!! I adopted your solution and implemented my java version. But it still took me some time to get an AC (besides, my code is horribly messy......I need to refine it, definitely.)
    I once stuck on two cases:

    "9,3,4,#,#,1,#,#,2,#,6,#,#"
    

    and

    "#, #"
    

    When dealing with consecutive # pair and and corner case, I had to be careful enough to check my stack state every time (empty or not?).

    public class Solution {
        public boolean isValidSerialization(String preorder) {
            if(preorder==null || preorder.length()==0)  return false;
            if(preorder.equals("#"))    return true;//empty tree, it is valid
            LinkedList<String> stack = new LinkedList<String>();
            String[] node = preorder.split(",");
            for(String s : node){
                if(!s.equals("#") || stack.size()==0){
                    stack.push(s);
                }else{
                    String t = stack.peek();
                    if(t.equals("#")){
                        while(stack.size()>0 && stack.peek().equals("#")){
                            if(pop2ele(stack)==false)   return false;
                        }
                        stack.push("#");
                    }else{
                        stack.push(s);
                    }
                }
            }
            if(stack.size()==1 && stack.peek().equals("#"))   return true;
            return false;
        }
        private boolean pop2ele(LinkedList<String> stack){
            if(stack.size()<2)  return false;
            stack.pop();
            stack.pop();
            return true;
        }
    }

  • 0
    N

    In the for loop, after appending s to stack, I guess you can do

    while len(stack) >= 3 and stack[-1] == stack[-2] == '#' and stack[-3] != '#':
    

    Pop 3 elements from stack and append '#' to stack for each while loop.
    Eventually, return stack == ['#']


  • 0
    R
    class Solution(object):
        def isValidSerialization(self, preorder):
            """
            :type preorder: str
            :rtype: bool
            """
            stack = []
            nodes = preorder.split(',')
            for x in nodes:
                stack.append(x)
                while len(stack) >= 3 and self.isNumber(stack[-3]) and stack[-2] == stack[-1] == '#':
                    stack.pop()
                    stack.pop()
                    stack[-1] = '#'
            return stack == ['#']
    
        def isNumber(self, s):
            try:
                int(s)
                return True
            except ValueError:
                return False

  • 0
    H

    Imagine input as "##". This is not a correct serialization of binary tree. But you cannot pop three elements since it will throw an error. So I am checking after two pops. I know my code can be shortened by combining multiple statements. Just for the sake of simplicity I have split that over a couple of lines.


  • 0
    N

    Yes, make sense. But I guess such input has been taken care of with the len(stack) >= 3 condition. And eventually, the stack would not equal to ['#'].


  • 2
    I

    Had the same idea as you. Here is a java version:

    public boolean isValidSerialization(String preorder) {
        String[]a = preorder.split(",");
        
        Stack<String> stack = new Stack<String>();
        for(int i = 0; i<a.length; i++){
            String cur = a[i];
            if(cur.equals("#")){
                while(!stack.isEmpty() && stack.peek().equals("#")){
                    stack.pop();
                    if(!stack.isEmpty()) stack.pop();
                    else return false;
                }
                stack.push("#");
            }else{
                stack.push(cur);
            }
        }
        return stack.size()==1 && stack.peek().equals("#");
    }

  • 3

    Here is my python solution with the same idea but shorter code:

    class Solution(object):
        def isValidSerialization(self, preorder):
            """
            :type preorder: str
            :rtype: bool
            """
            nodes, l = preorder.split(','), []
            for n in nodes:
                l.append(n)
                while len(l) > 2 and l[len(l) - 1] == "#" and l[len(l) - 2] == "#":
                    if l[-3] == "#":
                        return False
                    l = l[:-3]
                    l.append(n)
            return len(l) == 1 and l[0] == "#"
    

  • 0

    My Java version:

    public boolean isValidSerialization(String preorder) {
        if(preorder==null || preorder.length()==0) return false;
        String[] node=preorder.split(",");
        int[] stack=new int[node.length];
        int index=0;//index is top of stack
        for(String a : node){
            
            int tmp=index;
            while(tmp>=3 && stack[tmp-1]==0 && stack[tmp-2]==0 && stack[tmp-3]==1) {
                tmp-=2; 
                stack[tmp-1]=0;
            }
            index=tmp;
            
            if(a.equals("#")) {
                if(index>=2 && stack[index-1]==0 && stack[index-2]==1) {index--; stack[index-1]=0;}
                else                   stack[index++]=0;
            }else stack[index++]=1;
        }
        while(index>=3 && stack[index-1]==0 && stack[index-2]==0 && stack[index-3]==1) {
            index-=2; 
            stack[index-1]=0;
        }
        index--;
        return (index==0&&stack[0]==0)?true:false;
    }

  • 0
    R

    How if I use following code

    def isValidSerialization(idata):
        idata_list = idata.split(',')
        stack = []
        for element in idata_list:
            stack.append(element)
            if( len(stack) > 2 and stack[-1] == stack[-2] =='#' and stack[-3] != '#'):
                stack = stack[:-3]
                stack.append('#')
                if(len(stack) == 0 ):
                    return False
        return len(stack)==1 and stack[0] == '#'
    

    Mu input is "1,2,3,#,#,#,#,#,#"


  • 2
    V

    Hi, I am more interested in the thought process you'd to arrive at this solution. What is the intuition behind this approach and what made you thinking this push-pop-replace sequence? Anyone who got the intuition is welcome to help me. Thanks.


  • 0
    C

    A python generator solution

    def isValidSerialization(self, preorder):
            preorder = iter(preorder.split(','))
    
            def _dfs():
                node = next(preorder, None)
                if node is None:
                    return None
                if node == '#':
                    return '#'
                left = _dfs()
                right = _dfs()
                if left and right:
                    return node
                return None
            return _dfs() is not None and next(preorder, None) is None
    
    

  • 2
    H

    @vishal51 In very easy way I would say imagine popping from the stack as folding of the tree. The basic intuition was to collapse the entire tree into the root node.


  • 0
    W

    got some cleaner code

    class Solution(object):
        def isValidSerialization(self, preorder):
            """
            :type preorder: str
            :rtype: bool
            """
            p = preorder.split(',')
            stack = []
            for s in p:
                stack.append(s)
                while len(stack) > 1 and stack[-1] == '#' and stack[-2] == '#':
                    stack.pop()
                    stack.pop()
                    if not stack:
                        return False
                    stack[-1] = '#'
            return stack == ['#']
    

  • 0
    Z

    This can be slightly simplified. The key to simplify the code that uses stack is to solve the problem first and push data to stack at the end.

    def isValidSerialization(self, preorder):
        preorder, stack = preorder.split(","), []
        for node in preorder:
            while stack and node == stack[-1] == "#":
                stack.pop()
                if not stack: return False
                stack.pop()
            stack.append(node)
        return stack == ["#"]
    

  • 0
    D

    This is a brilliant solution. I could not wrap my head around the idea why the top element was replaced by # when you encounter two #'s and pop them out. After going through couple of example it clicked me (late) that by replacing the top with hash you are shrinking tree's child to null because you already process the child and all it's children.


Log in to reply
 

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