Thoughts from building tree and improve it step by step


  • 0
    D

    At first glance it reminds me of the previous question https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ which we can build a binary by different order. So the approach with inorder visit the preorder array came to my mind.

    We can store the parent node in a stack and once we have traversed the left subtree, we pop it up the parent, then we go to the right subtree. Finally we should reach the conclusion that the last element node should be a "#" and the stack is empty.

    public class Solution {
        public boolean isValidSerialization(String preorder) {
            String[] nodes = preorder.split(",");
            Stack<String> stack = new Stack<String>();
            
            for (int i = 0; i < nodes.length; i++) {
                if (nodes[i].equals("#")) {
                    if (i == nodes.length - 1) {
                        // last element case
                        return stack.isEmpty();
                    } else if (!stack.isEmpty()){
                        // pop up parent after finish left
                        stack.pop();
                    } else {
                        // stack is empty and we are at leave and stack is empty
                        return false;
                    }
                } else {
                    stack.push(nodes[i]);
                }
            }
            
            // other case which is not a valid tree like "1,2,3"
            return false;
        }
    } // finished 13ms
    

    then I realize I only use the stack for push and pop and don't use the info in it, so I replace the stack with a counter:

    public class Solution {
        public boolean isValidSerialization(String preorder) {
            String[] nodes = preorder.split(",");
            int count = 0;
            
            for (int i = 0; i < nodes.length; i++) {
                if (nodes[i].equals("#")) {
                    if (i == nodes.length - 1) {
                        return count == 0;
                    } else if (count > 0){
                        count--;
                    } else {
                        return false;
                    }
                } else {
                    count++;
                }
            }
            
            return false;
        }
    } // finished 11ms
    

    and finally I found for not '#' case, count only increase and in legal '#' case, count--. So I can simplify the code.

    public class Solution {
        public boolean isValidSerialization(String preorder) {
            String[] nodes = preorder.split(",");
            int count = 0;
            
            int i;
            for (i = 0; i < nodes.length; i++) {
                if (nodes[i].equals("#")) {
                    count--;
                    if (count < 0) {
                        break;
                    }
                } else {
                    count++;
                }
            }
            
            return i == nodes.length - 1;
        }
    } // finished 11ms
    

    which finally leads my answer similar to @dietpepsi 's answer: https://discuss.leetcode.com/topic/35976/7-lines-easy-java-solution/2 though his thought of degree is very smart


Log in to reply
 

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