我想知道二叉树T2是否是二叉树T1的子树。我读到可以使用预编序和按序遍历为T2和T1构建字符串表示，如果T2字符串是T1字符串的子字符串，则T2是T1的子树。
我对这种方法有点困惑，也不确定它的正确性。
来自wiki："树T的子树是由T中的一个节点及其在T中的所有子节点组成的树。">
在以下示例中：
T2:
1
/
2 3
T1:
1
/
2 3
4
如果我们为T2和T1构建字符串：
预购T2:"1,2,3">
预购T1:"1,2,3,4">
顺序T2:"2,1,3">
顺序T1:"2,1,3,4">
T2字符串是T1的子字符串，因此使用上面描述的子字符串匹配方法，我们应该得出T2是T1的子树的结论。
然而，根据定义，T2不应该是T1的子树，因为它没有T1根节点的所有子节点。
这里有一个相关的讨论，似乎得出了这个方法是正确的结论。
我是不是遗漏了什么？
非常有趣的问题。你似乎是对的。我想你提到的问题是由于数学(图论(和计算机科学中子树的不同定义引起的。在图论中，T2是T1的适当子树。
假设你从《破解编码面试》一书中得到了这一点，作者还提到，为了区分具有相同值的节点，还应该打印出空值。
这也可以解决子树的定义问题(正如书中所述，这是正确的(
预购T2:"1，2，null，null，3，null，null"预购T1:"1，2，null，null，3，null，4，null，null"顺序T2:"null，2，null，1，null，3，null"顺序T1："null，2，null，1，null，3，null，4，null">
正如您所看到的，T2不是T1 的子树
树的子树的定义应该与字符串的子字符串的定义相同。这样想：1.子字符串以开头、包含和结束。2.树也应该有相同的定义，但要通用以适应树的数据结构。3.从字符串的一维推广到树的二维推广。
我在读同一本书，也怀疑它的解决方案。我提出了另一个反例，它不属于用户icepack提到的潜在解释(子树不一定需要所有的子树(。
考虑以下树
T2:
B
/
A C
T1:
C
/
B C
/
A
预购T2:"BAC">
预购T1:"CBAC">
顺序T2:"ABC">
有序T1："ABCC">
同样，T2串是它们的T1对应物的子串，然而T2决不是T1的子树。也许作者已经排除了重复，并特别提到了他对子树的定义，这可能是正确的，但忽略了这些信息，我们别无选择，只能认为这是一个错误的解决方案。
首先
这个问题也来自《<Cracking the coding interview 6th>》一书的章节：IX Interview Questions|4. Trees and graphs|Question 4.10。
(这是谷歌软件工程师Gayle Laakmann McDowell的一本很棒的书，他采访了很多人。(
算法
-
(A(搜索根&匹配子树算法
复杂性：
-
时间
O(n + m*k)
最糟糕的情况很少发生O(n2 + m2*k2)
平均值，可能小于O(n + m)(来自其他算法(，但取决于
-
空间：
O(lg(m) + lg(n))
(主要由递归调用的方法堆栈获取。(
其中：
n
它有大树那么大m
它有小树那么大k
小树根在大树中出现的现象n2
在找到子树之前，在较大的树中搜索节点的次数
它在[1, n]之间m2
找到根时匹配的平均计数
对于随机输入，这应该非常小k2
在找到子树之前搜索到的根的出现次数
-
-
(B(分别遍历两个树到列表，并找到子列表
复杂性：
-
时间：
O(n + m) -
空间：
O(n + m))
其中：
n
它有大树那么大m
它有小树那么大
提示：
- 应该使用
pre-order遍历，还需要将null节点作为特殊值列出
否则，不同的树可能会输出相同的列表 in-order导线不起作用
因为它可能会为包含不同顺序的相同元素的树的不同输出输出相同的有序列表，即使空节点用特殊值表示也是如此
-
比较两种算法：
- A使用更少的内存，因此对于非常大的输入更具可扩展性
- A的速度不确定，但平均而言，它仍然可能比B快
- B的算法比较简单
代码
(以下是Java中的一个实现，包含两个算法和测试用例。(
CheckSubtree.java
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
/**
* Given 2 binary tree T1 & T2, they are very large, and T1 is much larger than T2.
* <p>Check whether T2 is a subtree of T1,
*
* @author eric
* @date 2/9/19 1:48 PM
*/
public class CheckSubtree {
/**
* Check whether small tree is subtree of large tree, via searching root & match.
* <p>Return on first match.
*
* @param largeTree large tree,
* @param smallTree small tree,
* @param <T>
* @return true if small tree is subtree of large tree, or small tree is empty,
*/
public static <T extends Comparable> boolean checkViaRootAndMatch(BST<T> largeTree, BST<T> smallTree) {
if (smallTree.size() == 0) return true; // small tree is empty,
BST.BSTNode<T> matchNode = searchAndMatch(largeTree.getRoot(), smallTree); // search root & try match,
return matchNode != null;
}
/**
* Search root, and check whether the subtree there match small tree.
*
* @param largeCurrent subtree of large tree,
* @param smallTree small tree,
* @param <T>
* @return node from large tree that match small tree, or null if not found,
*/
protected static <T extends Comparable> BST.BSTNode<T> searchAndMatch(BST.BSTNode<T> largeCurrent, BST<T> smallTree) {
if (largeCurrent == null) return null; // subtree of large is empty,
T smallRoot = smallTree.getRoot().getValue(); // value of small tree's root,
if (largeCurrent.getValue().compareTo(smallRoot) == 0) { // found root of small tree,
if (match(largeCurrent, smallTree)) return largeCurrent; // also match the whole small tree,
}
BST.BSTNode<T> leftFoundNode = searchAndMatch(largeCurrent.getLeft(), smallTree); // search in left subtree,
if (leftFoundNode != null) return leftFoundNode; // match in left subtree of current,
return searchAndMatch(largeCurrent.getRight(), smallTree); // search in right subtree,
}
/**
* Check whether small tree match at given subtree of large tree.
*
* @param largeCurrent subtree of large tree,
* @param smallTree small tree,
* @param <T>
* @return
*/
protected static <T extends Comparable> boolean match(BST.BSTNode<T> largeCurrent, BST<T> smallTree) {
return match(largeCurrent, smallTree.getRoot());
}
/**
* Check whether subtree of small tree match at given subtree of large tree.
*
* @param largeCurrent subtree of large tree,
* @param smallCurrent subtree of small tree,
* @param <T>
* @return true if subtree of small is subtree of large, or subtree of small is empty,
*/
protected static <T extends Comparable> boolean match(BST.BSTNode<T> largeCurrent, BST.BSTNode<T> smallCurrent) {
if (smallCurrent == null) return true; // smaller reach leaf,
if (largeCurrent == null) return false; // larger is empty, while smaller is not,
if (largeCurrent.getValue().compareTo(smallCurrent.getValue()) != 0)
return false; // current value is different,
if (!match(largeCurrent.getLeft(), smallCurrent.getLeft())) return false; // check whether left subtree match,
return match(largeCurrent.getRight(), smallCurrent.getRight()); // check whether right subtree match,
}
// traverse both tree and generate a list representation, then check whether the small list is sub list of large list,
/**
* Check whether small tree is subtree of large tree, via traverse tree to list & find sublist. Use given null value.
* <p>Return on first match.
*
* @param largeTree
* @param smallTree
* @param <T>
* @return
*/
public static <T extends Comparable> boolean checkViaTraverseAndSublist(BST<T> largeTree, BST<T> smallTree) {
return checkViaTraverseAndSublist(largeTree, smallTree, null);
}
/**
* Check whether small tree is subtree of large tree, via traverse tree to list & find sublist. Use given special value.
* <p>Return on first match.
*
* @param largeTree
* @param smallTree
* @param special special value to represent value of null node in tree,
* @param <T>
* @return
*/
public static <T extends Comparable> boolean checkViaTraverseAndSublist(BST<T> largeTree, BST<T> smallTree, T special) {
if (smallTree.size() == 0) return true; // small tree is empty,
// tree to list,
List<T> largeList = treeToList(largeTree, special);
List<T> smallList = treeToList(smallTree, special);
// System.out.printf("large list: %sn", largeList);
// System.out.printf("small list: %sn", smallList);
int idx = Collections.lastIndexOfSubList(largeList, smallList); // find sublist,
return idx >= 0;
}
/**
* Traverse tree and add nodes to list, with pre-order, use special value to represent null node.
*
* @param tree
* @param special special value to represent value of null node in tree,
* @param <T>
* @return
*/
protected static <T extends Comparable> List<T> treeToList(BST<T> tree, T special) {
List<T> list = new LinkedList<>();
treeToList(tree.getRoot(), special, list);
return list;
}
/**
* Traverse subtree and add nodes to list, with pre-order, use special value to represent null node.
*
* @param current
* @param special special value to represent value of null node in tree,
* @param list
* @param <T>
*/
protected static <T extends Comparable> void treeToList(BST.BSTNode<T> current, T special, List<T> list) {
if (current == null) {
list.add(special); // represent null with special value,
return;
}
list.add(current.getValue()); // current,
treeToList(current.getLeft(), special, list); // left subtree,
treeToList(current.getRight(), special, list); // right subtree,
}
}
CheckSubtreeTest.java
(单元测试，通过TestNG(
import org.testng.Assert;
import org.testng.annotations.BeforeMethod;
import org.testng.annotations.Test;
/**
* CheckSubtree test.
*
* @author eric
* @date 2/9/19 4:18 PM
*/
public class CheckSubtreeTest {
private int n = 10;
// trees, via minimal BST,
private BST<Integer> largeTree; // large tree,
private BST<Integer> smallTree; // small tree, subtree of large tree,
private BST<Integer> smallTree2; // small tree, not subtree of large tree,
private BST<Integer> emptyTree; // empty tree,
@BeforeMethod
public void init() {
// init - large tree,
largeTree = CreateMinimalBST.createRangeNum(0, n);
// init - small tree,
smallTree = CreateMinimalBST.createRangeNum(8, 10);
smallTree2 = CreateMinimalBST.createRangeNum(2, 5);
// init empty BST,
emptyTree = new BST<>();
}
// checkViaRootAndMatch(),
@Test
public void testViaRootAndMatch() {
Assert.assertTrue(CheckSubtree.checkViaRootAndMatch(largeTree, smallTree)); // subtree,
Assert.assertFalse(CheckSubtree.checkViaRootAndMatch(largeTree, smallTree2)); // not subtree,
Assert.assertFalse(CheckSubtree.checkViaRootAndMatch(smallTree, largeTree)); // not subtree,
// empty tree,
Assert.assertTrue(CheckSubtree.checkViaRootAndMatch(largeTree, emptyTree));
Assert.assertTrue(CheckSubtree.checkViaRootAndMatch(smallTree, emptyTree));
Assert.assertTrue(CheckSubtree.checkViaRootAndMatch(emptyTree, emptyTree));
}
// checkViaTraverseAndSublist(),
@Test
public void testViaTraverseAndSublist() {
// Integer special = null;
// Integer special = Integer.MAX_VALUE;
Assert.assertTrue(CheckSubtree.checkViaTraverseAndSublist(largeTree, smallTree)); // subtree,
Assert.assertFalse(CheckSubtree.checkViaTraverseAndSublist(largeTree, smallTree2)); // not subtree,
Assert.assertFalse(CheckSubtree.checkViaTraverseAndSublist(smallTree, largeTree)); // not subtree,
// empty tree,
Assert.assertTrue(CheckSubtree.checkViaTraverseAndSublist(largeTree, emptyTree));
Assert.assertTrue(CheckSubtree.checkViaTraverseAndSublist(smallTree, emptyTree));
Assert.assertTrue(CheckSubtree.checkViaTraverseAndSublist(emptyTree, emptyTree));
}
}
所有测试用例都将通过。
提示：
- CCD_ 25是一个简单的二叉树impl
BST.BSTNode是BST的节点CreateMinimalBST是一个帮助构建最小高度的二进制搜索树的工具
Na。。。这种做法是不正确的。因为，不同的树可以有相同的遍历。例如，在给定的例子中，树是
26
/
10 3
/
4 6 3
30
并且候选子树是
10
/
4 6
30
和
30
/
4 10
6
具有与4,30,10,6相同的有序遍历但第二个不是子树