《Cracking the Coding Interview》——第4章：树和图—

《Cracking the Coding Interview》——第4章：树和图——题目8

2014-03-19 05:04

题目：给定两棵二叉树T1和T2，判断T2是否是T1的子树。子树的定义是，以T1的某个节点(可以是T1的根)作为根节点，得到的这棵树和T2一模一样。

解法：首先可以根据节点个数省去一大部分不必要的搜索，然后再递归判断。代码还比较简单，请看下面。

代码：

  1 // 4.8 Check if a tree is a subtree of another.
  2 #include <cstdio>
  3 #include <unordered_map>
  4 using namespace std;
  5 
  6 struct TreeNode {
  7     int val;
  8     TreeNode *left;
  9     TreeNode *right;
 10     
 11     TreeNode(int _val = 0): val(_val), left(nullptr), right(nullptr) {};
 12 };
 13 
 14 void constructTree(TreeNode *&root)
 15 {
 16     int val;
 17     
 18     scanf("%d", &val);
 19     if (val == 0) {
 20         root = nullptr;
 21     } else {
 22         root = new TreeNode(val);
 23         constructTree(root->left);
 24         constructTree(root->right);
 25     }
 26 }
 27 
 28 int countNode(TreeNode *root, unordered_map<TreeNode *, int> &node_count)
 29 {
 30     if (root == nullptr) {
 31         return 0;
 32     } else {
 33         node_count[root] = countNode(root->left, node_count) + countNode(root->right, node_count) + 1;
 34         return node_count[root];
 35     }
 36 }
 37 
 38 bool isIdentical(TreeNode *root1, TreeNode *root2)
 39 {
 40     if (root1 == nullptr) {
 41         return root2 == nullptr;
 42     } else if (root2 == nullptr) {
 43         return false;
 44     }
 45     
 46     if (root1->val != root2->val) {
 47         return false;
 48     }
 49     
 50     return isIdentical(root1->left, root2->left) && isIdentical(root1->right, root2->right);
 51 }
 52 
 53 bool hasSubtree(TreeNode *root1, TreeNode *root2, unordered_map<TreeNode *, int> &node_count)
 54 {
 55     if (root1 == nullptr || root2 == nullptr) {
 56         return false;
 57     }
 58     
 59     if (node_count[root1] < node_count[root2]) {
 60         return false;
 61     } else if (node_count[root1] > node_count[root2]) {
 62         return hasSubtree(root1->left, root2, node_count) || hasSubtree(root1->right, root2, node_count);
 63     } else {
 64         return isIdentical(root1, root2);
 65     }
 66 }
 67 
 68 void clearTree(TreeNode *&root)
 69 {
 70     if (root == nullptr) {
 71         return;
 72     }
 73     clearTree(root->left);
 74     clearTree(root->right);
 75     delete root;
 76     root = nullptr;
 77 }
 78 
 79 int main()
 80 {
 81     TreeNode *root1, *root2;
 82     unordered_map<TreeNode *, int> node_count;
 83     
 84     while (true) {
 85         constructTree(root1);
 86         if (root1 == nullptr) {
 87             break;
 88         }
 89         constructTree(root2);
 90         if (root2 == nullptr) {
 91             break;
 92         }
 93         
 94         countNode(root1, node_count);
 95         countNode(root2, node_count);
 96         if(hasSubtree(root1, root2, node_count)) {
 97             printf("Yes
");
 98         } else {
 99             printf("No
");
100         }
101         
102         node_count.clear();
103         clearTree(root1);
104         clearTree(root2);
105     }
106     
107     return 0;
108 }