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(",");
            pt=0;
            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.