Java Simple Preorder Traversal without building the tree

  • 0

    Just traditional Preorder Traversal without building the tree.

    public class Solution {
        private int pt;
        public boolean isValidSerialization(String preorder) {
            if(preorder==null||preorder.length()==0) return true;
            String[] nodes=preorder.split(",");
            return preorderTraversal(nodes) && pt==nodes.length; //Check if we have used all the nodes
        private boolean preorderTraversal(String[] nodes){
            if(pt>=nodes.length) return false;
            else if(nodes[pt++].equals("#")) return true;
            boolean leftIsValid=preorderTraversal(nodes);
            boolean rightIsValid=preorderTraversal(nodes);
            return leftIsValid&&rightIsValid; //each non-null node must have both left child and right child (can be null node)

Log in to reply

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