Simple O(n) Solution


  • 19
    J

    Use iterative preorder traversal, actually no need to use stack, just a integer to track the depth of the stack.

    public class Solution {
        public boolean isValidSerialization(String preorder) {
            if (preorder == null || preorder.length() == 0) return false;
            String[] strs = preorder.split(",");
            int depth = 0;
            int i = 0; 
            while (i < strs.length - 1) {
                if (strs[i++].equals("#")) {
                    if (depth == 0) return false;
                    else depth--;
                }
                else depth++;
            }
            if (depth != 0) return false;
            return strs[strs.length - 1].equals("#");
        }
    }

  • 0
    R

    Kindly explain the solution
    if the tree is like - 9,3,4,#,#,1#,#,2,#,6,#,# then your explanation works i.e the variable depth shows the size of stack just before that number is popped but consider this case - 10,8,3,#,#,#,2,5,#,#,# here the explanation fails but the algorithm still gives the correct answer.
    Though it works,kindly explain the solution.


  • 0
    J

    in your 2nd case, I think you are confused with the stack when the depth is zero, that means you have just pop out the root, next step is go to the right of the root, which is 2 and push 2 into stack.

    you can not pop when stack is empty. But stack can be empty if next operation is push. Only the last element of the array is the corner case, which is always "#" and tries to pop when stack is empty.

    Hopefully it expains your confusing.


  • 0
    J

    Inside a tree, once we got a '#', we must have a tree node. So we just compare their amounts through stack. And since leaves are one more than nodes inside, so we have to make sure the last one is '#'


  • 0
    O

    Sorry I don't follow your mind.
    for example "9##"

    when you iterate to "9" depth++ -> 1
    when you iterate to "#" depth-- ->0
    depth == 0 now you return false.
    Thus your code fails. Please tell me where am I wrong.


  • 0
    J

    while loop is terminated before last "#":
    i < strs.length - 1
    The last "#" is treated specially.


Log in to reply
 

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