树的子结构

ryluo 2020-06-27 17:51:18

输入两棵二叉树A,B,判断B是不是A的子结构。

我们规定空树不是任何树的子结构。

样例

树A:

     8
    / \
   8   7
  / \
 9   2
    / \
   4   7

树B:

   8
  / \
 9   2

返回 true ,因为B是A的子结构。

分析:

遍历树中的每个节点,判断当该节点为根节点是否可以与子树相互匹配。

判断是否会与子树相互匹配,再使用递归遍历的方法取判断。

详细题解:https://www.acwing.com/solution/content/745/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if(!pRoot1 || !pRoot2) return false;
        if(isPart(pRoot1, pRoot2)) return true;
        return hasSubtree(pRoot1->left, pRoot2) || hasSubtree(pRoot1->right, pRoot2);
    }

    bool isPart(TreeNode* p1, TreeNode* p2){
        if(!p2) return true;
        if(!p1 || p1->val != p2->val) return false;
        return isPart(p1->left, p2->left) && isPart(p1->right, p2->right);
    }
};