我想知道二叉树 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 的真子树。
假设你是从《Cracking the Coding Interview》一书中得到的，作者还提到要区分具有相同值的节点，还应该打印出空值。
这也可以解决您定义子树的问题（这也是正确的，如书中所述）
前序 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 的子树
I'm reading the same book and doubted its solution as well. I came up with another counter-example that doesn't fall into the potential interpretation that user icepack mentions (of a subtree not necessarily needing all the descendents).
Consider the following trees
T2:
B
/ \
A C
T1:
C
/ \
B C
/
A
preorder T2: 'BAC'
preorder T1: 'CBAC'
inorder T2: 'ABC'
inorder T1: 'ABCC'
Again, the T2 strings are substrings of their T1 counterparts and yet T2 is in no way a subtree of T1. Perhaps in the author had ruled out duplicates and specifically mentioned his definition of subtree it could be right, but leaving out that information leaves us with no choice but to consider it an incorrect solution.
树的子树的定义应该与字符串的子串的定义相同。可以这样想： 1. 子字符串有开头、包含和结尾。2. 树也应该具有相同的定义，但一般化以适应树数据结构。3. 泛化是从字符串的一维到树的二维。
问题也来自 book<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))
主要由递归调用的方法堆栈占用。）
在哪里：
nmkn2[1, n]。m2k2(B) 分别遍历两棵树到列表，找到子列表。
复杂：
时间： O(n + m)
空间： O(n + m))
在哪里：
nm提示：
pre-order遍历，并且还需要将空节点作为特殊值列出。in-order遍历将不起作用。比较两种算法：
（以下是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: %s\n", largeList);
// System.out.printf("small list: %s\n", 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));
}
}
所有测试用例都会通过。
提示：
BST是一个简单的二叉树impl。BST.BSTNode是BST的节点。CreateMinimalBST是一个帮助构建最小高度的二叉搜索树的工具。不...这种方法是不正确的。因为，不同的树可以有相同的遍历。例如，在给定的示例中，树是
26
/ \
10 3
/ \ \
4 6 3
\
30
并且候选子树是
10
/ \
4 6
\
30
和
30
/ \
4 10
\
6
具有与 4,30,10,6 相同的中序遍历，但第二个不是子树