Verify Preorder Serialization of a Binary Tree

Verify Preorder Serialization of a Binary Tree

题目链接:https://leetcode.com/problems...

recursion,用个全局的index:

public class Solution {
    public boolean isValidSerialization(String preorder) {
        if(preorder == null || preorder.length() == 0) return false;
        String[] tree = preorder.split(",");
        if(tree.length == 1) return tree[0].equals("#");
        
        return dfs(tree) && tree.length == index;
    }
    int index = 0;
    private boolean dfs(String[] tree) {
        // start from root
        if(index >= tree.length) return false;
        if(tree[index].equals("#")) {
            index++;
            return true;
        }
        index++;
        return dfs(tree) && dfs(tree);
    }
}

iteration:

public class Solution {
    public boolean isValidSerialization(String preorder) {
        if(preorder == null || preorder.length() == 0) return false;
        // iteration, add the node
        Stack<String> stack = new Stack();
        for(String s : preorder.split(",")) {
            // check 2 "#"
            if(s.equals("#")) {
                while(!stack.isEmpty() && stack.peek().equals("#")) {
                    // pop "#"
                    stack.pop();
                    if(stack.isEmpty()) return false;
                    // pop parent of "#" & "#"
                    stack.pop();
                }
            }
            stack.push(s);
        }
        
        return stack.size() == 1 && stack.peek().equals("#");
    }
}

看到discussion还有一种用入度出度的方法,比较厉害,不用额外空间:
除了根节点和叶子节点之外,每个节点都有2个出度(left,right)和1个入度,根节点非空有2个出度0个入度,叶子节点有1个入度。令diff = outdegree - indegree,那么从累加diff会一直保持正,最后为0。从左往右比较好理解,因为preorder总是总root到左再到右,root的diff总是>0的,所以一定是保持positive。从右往左就不知道怎么理解了。。注意diff从1开始,因为root没有indegree。

public class Solution {
    public boolean isValidSerialization(String preorder) {
        int diff = 1;
        for(String s : preorder.split(",")) {
            if(--diff < 0) return false;
            if(!s.equals("#")) diff += 2;
        }
        return diff == 0;
    }
}
相关文章
相关标签/搜索