判断一棵树是否为另一棵树的子结构

发表于 | 分类于 | 评论数： | 阅读次数： | 阅读次数：

LeetCode 572. Subtree of Another Tree

实现一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool isSubtree(TreeNode* s, TreeNode* t) {
    if (!s) {
        return false;
    }
    if (isSame(s, t)) {
        return true;
    }
    return isSubtree (s->left, t) || isSubtree(s->right, t);
}
bool isSame (TreeNode* s, TreeNode* t) {
    if (!s && !t) {
        return true;
    }
    if (!s || !t) {
        return false;
    }
    if (s->val != t->val) {
        return false;
    }
    return isSame (s->left, t->left) && isSame(s->right, t->right);
}

这道题让我们求一个数是否是另一个树的子树，从题目中的第二个例子中可以看出，子树必须是从叶结点开始的，中间某个部分的不能算是子树，那么我们转换一下思路，是不是从s的某个结点开始，跟t的所有结构都一样，那么问题就转换成了判断两棵树是否相同，也就是Same Tree的问题了，这点想通了其实代码就很好写了，用递归来写十分的简洁，我们先从s的根结点开始，跟t比较，如果两棵树完全相同，那么返回true，否则就分别对s的左子结点和右子结点调用递归再次来判断是否相同，只要有一个返回true了，就表示可以找得到。

实现二

The question is exactly similar to the Leetcode 100 Same Tree
Solution for Leetcode 100: https://leetcode.com/problems/same-tree/discuss/148340/CPP-Easy-to-Understand

Also Check Leetcode 101 [Symmetric Tree]https://leetcode.com/problems/symmetric-tree/description/) Leetcode 101 eh? :P

Okay so now you will be absolutely comfortable with this question. It just requires you to

1.Start with a node of tree s (lets call this s-node)
2.Compare the trees forming with root s-node and root t
3.If the trees match(leetcode 100 logic) then return true
4.Else go to step one and check for s->left || s->right

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if(!s) return false;
        return isSameTree(s,t) || isSubtree(s->left,t) || isSubtree(s->right,t);
    }
    
    //Leetcode 100
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p==NULL && q==NULL)
            return true;
        if(p==NULL || q==NULL)
            return false;
        if(p->val == q->val)
            return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
        else
            return false;
    }
    
};

LeetCode 101. Symmetric Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool isSymmetric(TreeNode* root) {
       if (root == nullptr) {
           return true;
       }
       return helper (root->left, root->right);
   }
   bool helper (TreeNode* left, TreeNode* right) {
       if (left == nullptr && right == nullptr) {   //两边同时为空，说明同时到头了，能走到这一步说明那些return false的不对称条件都没满足（也就是说到这为止这棵树是对称的）。
           return true;
       }
       if (left == nullptr || right == nullptr) {  //有一个是空的（那就两边不对称了）
           return false;
       }
       if (left->val == right->val) {  //对称位置数值相等， 更新参数，继续前进。
           return helper (left->left, right->right) && helper (left->right, right->left);
       } else 
           return false;
   
               
   }
0%