c**y
发帖数: 172 | 1 I come up with some questions when considering the following problem. A
related discussion is found here
http://stackoverflow.com/questions/1017821/find-whether-a-tree- but I didn't find the answer to my particular questions.
Problem: given two binary trees T1 (large) and T2 (small), how do we check
whether or not T2 is a subtree of T1? Brutal force solution is out of scope
of this post. Another solution is as follows. A general idea is to serialize
T1 and T2 into two arrays A(T1) and A(T2) first, and then check if A(T2) is
a substring of A(T1). This solution is discussed here, http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-of-another-binary-tree/. According to Himanshu's post at above URL, we need to process these arrays slightly differently.
Following Himanshu's solution, we can serialize a binary tree with some
special processes: When serializing a binary tree in any order, use ‘(‘/‘
)’ to represent the left/right NULL children in the serialized array. We
use InOrderSA(T)/PreOrderSA(T)/PostOrderSA(T) to denote the specially
processed inorder/preorder/postorder arrays. For example, the special
inorder array of a tree T
2
/ \
1 3
is InOrderSA(T) = (1)2(3)
The special preorder array of a tree T'
2
\
3
is PreOrderSA(T') = 2((3)
Here are my questions
1. Does the array InOrderSA(T) alone determine a binary tree T WITHOUT
duplicate elements uniquely? If yes, do PreOrderSA(T) and PostOrderSA(T)
achieve the same thing?
2. Does the array InOrderSA(T) alone determine a binary tree T WITH
duplicate elements uniquely?
Your input is highly appreciated! | c**y
发帖数: 172 | | l**b
发帖数: 457 | 3 这种题目，我可以说不能用json啊？会不会被直接藐视？ | j********x
发帖数: 2330 | | j********x
发帖数: 2330 | |
|
