使用preorder和序串检查子树 [英] checking subtrees using preorder and inorder strings

问题描述

这本书我读的权利要求的一个方法来检查二叉树 B 是二进制树的树 A 是构建序和 preorder 的字符串（即重新present字符串序和$每棵树的对$ porder遍历）这两个目录树，并检查是否 inorder_B 是 inorder_A 的子和 preorder_B 是 preorder_A 的子字符串。请注意，它声称，你必须检查两个中序和 preorder字符串。

A book I'm reading claims that one way to check whether a binary tree B is a subtree of a binary tree A is to build the inorder and preorder strings (strings that represent the inorder and preorder traversal of each tree) of both trees, and check whether inorder_B is a substring of inorder_A and preorder_B is a substring of preorder_A. Note that it claims that you have to check substring match on both the inorder and preorder strings.

难道真的有必要检查一个字符串匹配上的两个中序和preorder字符串？那岂不是不够的检查要么？可能有人提供了一个例子来证明我是错的（即证明在书的请求权）？我不能想出一个例子，其中两棵树是不平等的，但preorder或序字符串匹配。

Is it really necessary to check for a substring match on both the inorder and preorder strings? Wouldn't it suffice to check either? Could someone provide an example to prove me wrong (i.e. prove the claim in the book right)? I couldn't come up with an example where two trees were unequal but the preorder or inorder strings match.

推荐答案

考虑二两节点树A和B为节点。树人有b以根和A为离开孩子。树上有两个具有A作为根和B右孩子。中序遍历匹配，但树木不同。

Consider the two two node trees with A and B as nodes. Tree one has B as root and A as left child. Tree two has A as root and B as right child. The inorder traversals match but the trees differ.

这篇关于使用preorder和序串检查子树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！