C# simple solution


  • 0
    S

    For every node, there should be 2 children. In case of following two conditions; it's an invalid tree

    1. If you find any node without 2 children
    2. If all nodes have got 2 children and still there is some traversal left.

    Based on this, I am simply using a stack which has nothing but a count. If you get a number, push 0 on the stack. When you get '#', pop the last value, increment the count. Pop all values which have count = 2, and push back the value which is 1 i.e. only one child is yet found. In the end if the stack is empty, it's a valid traversal otherwise not.

    public class Solution {
        public bool IsValidSerialization(string preorder) {
            Stack<int> allNodes = new Stack<int>();
            string[] chunks = preorder.Split(',');
            
            for (int i = 0; i < chunks.Length; i++){
                if (i != 0 && allNodes.Count == 0){
                    return false;
                }
                if (chunks[i] != "#"){
                    allNodes.Push(0);
                }else{
                    while(allNodes.Count != 0){
                        int last = allNodes.Pop();
                        last = last + 1;
                        if (last == 1){
                            allNodes.Push(last);
                            break;
                        }
                    }
                }
            }
            
            return allNodes.Count == 0;
        }
    }
    

Log in to reply
 

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