Title: Verify Preorder Serialization of a Binary Tree Source: leetcode.com
One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as #.
|
1 2 3 4 5 6 7 |
_9_ / \ 3 2 / \ / \ 4 1 # 6 / \ / \ / \ # # # # # # |
For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node.
Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.
Each comma separated value in the string must be either an integer or a character '#' representing null pointer.
You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".
Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true
Example 2:
"1,#"
Return false
Example 3:
"9,#,#,1"
Return false
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
/* https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/ */ import java.util.Stack; public class VerifyPreorderSerialization { //the idea is to use a stack and push the element into the stack when the //the current item is not equal to "#" and when the current item is equal //to the "#", then check the top element on the stack public boolean isValidSerialization(String preorder) { Stack<String> stack = new Stack<String>(); String[] s = preorder.split(","); //if the length of array is 0 //then there is no node in the binary tree //return false if(s.length==0) { return false; } //if the length of the array is 1 //check if s[0] is equal to "#", then tree consists of null node //check if s[0] is not equal to "#", then return false (valid binary //tree with single node will have "9,#,#") if(s.length==1) { if(s[0].equals("#")) return true; else return false; } //push the first element in the array into the stack stack.push(s[0]); for(int i=1;i<s.length;i++) { //if s[i] is not equals to "#", then push if(!s[i].equals("#")) { stack.push(s[i]); } //if s[i] is equals to "#" else if(s[i].equals("#")) { //then check if the top element on the stack is not equals //to "#" if(!"#".equals(stack.peek())) { stack.push(s[i]); } //if the top element on the stack is equals to "#" //then call pushPoundSymbol else { if(!pushPoundSymbol(stack, s[i])) return false; } } } if(stack.size()==1 && "#".equals(stack.peek())) return true; else return false; } public boolean pushPoundSymbol(Stack<String> stack, String symbol) { //if the stack is empty or the top element in the stack is not equals //to "#" then push the symbol on to the stack if(stack.isEmpty() || !"#".equals(stack.peek())) { stack.push(symbol); } else { //check if the size of the stack is greater than 1 if(stack.size()>1) { //pop the top element that ie "#" and check if the next top //element is not "#" stack.pop(); //if the top element is not "#" then pop the top element //else return false if(!"#".equals(stack.peek())) stack.pop(); else return false; return pushPoundSymbol(stack, "#"); } else return false; } return true; } public static void main(String args[]) { VerifyPreorderSerialization v = new VerifyPreorderSerialization(); //String serializedString = "9,3,4,#,#,1,#,#,2,#,6,#,#"; String serializedString = "4,#,#,1"; System.out.println(v.isValidSerialization(serializedString)); } } |
Python solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
''' https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/ ''' class Solution(object): def isValidSerialization(self, preorder): """ :type preorder: str :rtype: bool """ lst = [] index = -1 preorder = preorder.split(",") ln = len(preorder) root_flag = False if len(preorder) == 1 and preorder[0] == '#': return True for i,c in enumerate(preorder): # enumerate over each element in preorder tree if c == '#': if not lst: return False lst[-1].append(True) while index >= 0 and len(lst[-1]) > 2: lst.pop() index -= 1 if index == -1 and i + 1 != ln: return False else: root_flag = True if lst: x = lst[index] x.append(True) index += 1 lst.append([c]) while index >= 0: x = lst[index] if len(x) == 3: index -= 1 else: break return not (index >= 0) |
Now it is known to me that articles is nothing but inspiring is everything to do something great.Thanks for sharing that wonderful useful information,given programming coding was very excellent and easily observe all provided information.
You have shared useful programming with us. Thanks for your effort.
Thank You! 🙂
Pingback: N-ary Tree PreOrder Traversal - Coddicted