LeetCode

LeetCode-判断是否是子树

有两棵树，A和B，判断B是否是A的子树。
如下图左为A，右为B：

1
2
3
4
5
6
7
    5
   / \
  4   6           4
 / \   \         / \
7   8   9       7   8
   / \
  1   2

有两种情况：

  1. B 可以只是A子树的一部分。那么上例中B是A的子树。
  2. B 严格是A的子树。那么上例中B不是A的子树。

思路

两种情况主题思路是一样的：
第一步，在Ａ中找与B的根节点一样的结点。先序遍历，如果B的根节点与Ａ的当前结点不同，那么分别考察Ａ的左子树和右子树。

第二步，当在Ａ中找到B的根节点一样的结点Ｒ后，判断Ａ以Ｒ为树根的子树是否与Ｂ相同。此时就要区分上述两种情况了。

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    // 先序遍历找到R
    bool findR(Node* s, Node* t) {
        if (!s && !t) return false;
        if (!s || !t) return false;

        bool res = false;

        if (s->val == t->val) {
            res = isSubTree(s, t);
        }
        if (!res) res = findR(s->left, t);
        if (!res) res = findR(s->right, t);

        return res;
    }

private:
    bool isSubTree(Node* a, Node* b) {
        
        /// relativaly equal 第一种情况
        if (a==nullptr && b==nullptr) return true;
        if (a==nullptr && b!=nullptr) return false;
        if (a!=nullptr && b==nullptr) return true; 

        /// absolutly equal 第二种情况
        //if (a==nullptr && b==nullptr) return true;
        //if ((!a && b) || (a && !b)) return false;  

        if (a->val != b->val) return  false;
        return isSubTree(a->left, b->left) && isSubTree(a->right, b->right);
    }
};

注意：

  1. 只要访问一个对象，就要提前判断这个对象是否合法。
  2. 树的问题绝大数情况是要对数进行遍历，上述问题就是先序遍历。
  3. 注意递归返回值，返回值是bool型，