Traversal solution but not building a tree


  • 3
    D
    public class Solution {
        int idx;
        public boolean isValidSerialization(String preorder) {
            String[] strs = preorder.split(",");
            if (strs.length == 0) return true;
            if (strs.length == 1) {
                if (strs[0].equals("#")) return true;
                else return false;
            }
            idx = 0;
            return preorder(strs) && (idx == strs.length);
        }
        boolean preorder(String[] strs) {
            if (idx == strs.length) return true;
            if (strs[idx].equals("#")) {
                idx++;
                return true;
            }
            idx++;
            if (idx == strs.length) return false;
            boolean left = preorder(strs);
            if (idx == strs.length) return false;
            boolean right = preorder(strs);
            return left && right;
        }
    }

  • 0
    B

    I have a very similar solution like yours

    public class Solution {
      private int currentIndex;
    
      public boolean isValidSerialization(String preorder) {
        String[] nodes = preorder.split(",");
        return isValidSerialization(nodes) && currentIndex == nodes.length;
      }
    
      public boolean isValidSerialization(String[] nodes) {
        if (currentIndex >= nodes.length) {
          return false;
        }
    
        String node = nodes[currentIndex++];
        if ("#".equals(node)) {
          return true;
        }
    
        //Ensure that we have both left and right node
        return isValidSerialization(nodes) && isValidSerialization(nodes);
      }
    }
    

Log in to reply
 

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