331. Verify Preorder Serialization of a Binary Tree - cocoder39/coco39_LC GitHub Wiki

331. Verify Preorder Serialization of a Binary Tree

method 1 uses stack

  • if current token is a number n, push it into stack since it cannot produce any violation. Now n is the root of a sub tree.
  • if current token is '#', check the top of stack:

if top is a number n, then '#' is the left null child of sub tree whose root is n. if top is also a '#', then the '#' on the top must be the left null child and current token '#' must be the right null child. pop top '#', the next top must be the root a this sub tree. if (s.empty() || s.top() == '#')

  • finally the stack should only contain a single '#', return s.size() == 1 && s.top() == '#' 
     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

tip: use stringstream ss(preorder), while (getline(ss, token, ',')) to split the string

time is O(n) and space is O(n)

bool isValidSerialization(string preorder) {
        stack<char> s;
        stringstream ss(preorder);
        
        string token;
        while (getline(ss, token, ',')) {
            if (token != "#") { //a new root
                s.push('n');
            }
            else { //token == '#'
                while (! s.empty() && s.top() == '#') { //left null child
                    s.pop();
                    if (s.empty() || s.top() == '#') { //must be a root
                        return false;
                    }
                    s.pop();
                }
                s.push('#');
            }
        }
        return s.size() == 1 && s.top() == '#';
    }

method 2 depends on indegree / outdegree

view null node as leave,then the tree is a completed tree.

  • each node (excepts root of tree) has 1 indegree
  • a null node has 0 outdegree
  • a not-null node has 2 outdegree
  • diff = outdegree - indegree, diff should never be less than 0, the final diff should be 0

tip: initialize diff with 1, which can overcome the first if (--diff < 0)

bool isValidSerialization(string preorder) {
        //each node (excepts root of tree) has 1 indegree
        //a null node has 0 outdegree
        //a not-null node has 2 outdegree
        stringstream ss(preorder);
        string token;
        int diff = 1;
        while (getline(ss, token, ',')) {
            if (--diff < 0) { //indegree is 1
                return false;
            }
            if (token != "#") { //outdegree is 2
                diff += 2;
            }
        }
        return diff == 0;
    }

follow up:

  • verify postorder. same idea!
  • what if inorder? #,1,#,2,#? it can be either rooted with 1 or 2, hard to handle
⚠️ **GitHub.com Fallback** ⚠️