Consider from behind...


  • 0
    H

    Similar idea but consider it differently.

    Starting from the end, each time there's a number, the method converts a simple node (num, #, #) to null node (#), hence number of # decrease by 1.
    Once the process start, number of # cannot be less than 1. (# can only decrease from 2 to 1, but cannot vanish itself.)
    Example:
    "9,3,4,#,#,1,#,#,2,#,6,#,#"
    (6,#,# --> #)
    "9,3,4,#,#,1,#,#,2,#,#"
    (2,#,# --> #)
    "9,3,4,#,#,1,#,#,#"
    (1,#,# --> #)
    "9,3,4,#,#,#,#"
    (4,#,# --> #)
    "9,3,#,#,#"
    (3,#,# --> #)
    "9,#,#" (binary tree: root = 9, left = null, right = null)
    (9,#,# --> #)
    "#" (binary tree: root = null)

        public boolean isValidSerialization(String preorder) {
            String[] strs = preorder.split(",");
            int leaf = 0; // consider "#" as leaf, count the number of "#"
            for (int i = strs.length - 1; i >= 0; i--) {
                if (strs[i].equals("#")) {
                    leaf++;
                } else {
                    if (--leaf <= 0) return false;
                }
            }
            return leaf == 1; // one node left
        }
    

Log in to reply
 

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