Share my solution, easy to understand.


  • 0
    K

    Check the tokens from end. Use nodeNum as the number of leaf nodes. If "#", increase nodeNum by 1; otherwise two leaf nodes should be "consumed". Return false If nodeNum less than 2. After two leaf nodes are "consumed", we get a new leaf nodes so decrease nodeNum only by 1. In the end we should have only one node left.

    public class Solution {
        public boolean isValidSerialization(String preorder) {
            String[] token = preorder.split(",");
            int nodeNum = 0;
            for (int i = token.length - 1; i >= 0; --i){
                if (token[i].equals("#")) nodeNum++;
                else {
                    if (nodeNum < 2) return false;
                    nodeNum--;
                }
            }
            return nodeNum == 1;
        }
    }

Log in to reply
 

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