Leetcode题解剑指 Offer 26. 树的子结构

PROBLEM

难度中等

MY ANSWER

使用bfs遍历A，找到与B头节点值相等的节点，调用judge，分别使用bfs遍历进行比较。若有一次judge调用返回true，则说明A包含B。M为A节点数，N为B节点数，时间复杂度O(MN)，空间复杂度O(M)。

/**
 * 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 judge(TreeNode* A, TreeNode* B) {
        queue<TreeNode*> m;
        queue<TreeNode*> n;
        m.push(A);
        n.push(B);
        while(1) {
            TreeNode* anode = m.front();
            TreeNode* bnode = n.front();
            if(!anode && bnode) {
                //cout<<"ji1"<<endl;
                return false;
            }
            if(anode && !bnode) {
                m.pop();
                n.pop();
                if(n.empty()) {
                    break;
                }
                continue;
            }
            if(!anode && !bnode) {
                m.pop();
                n.pop();
                if(n.empty()) {
                    break;
                }
                continue;
            }
            if(anode->val != bnode->val) {
                //cout<<"ji2"<<endl;
                return false;
            }
            else {
               m.pop();
               m.push(anode->left);
               m.push(anode->right);
               n.pop();
               n.push(bnode->left);
               n.push(bnode->right);
            }
            if(m.empty()) {
                break;
            }
        }
        return true;
    }

    bool isSubStructure(TreeNode* A, TreeNode* B) {
        int flag = 0;
        queue<TreeNode*> tmp;
        tmp.push(A);
        if(!B || !A) {
            return false;
        }
        while(!tmp.empty()) {
            TreeNode* node = tmp.front();
            if(node == NULL) {
                //cout<<"null"<<endl;
                tmp.pop();
            }
            else if(node->val == B->val) {
                //cout<<"judge"<<endl;
                flag += judge(node, B);
                tmp.pop();
                tmp.push(node->left);
                tmp.push(node->right);
            }
            else {
                //cout<<"none"<<endl;
                tmp.pop();
                tmp.push(node->left);
                tmp.push(node->right);
            }
        }
        //cout<<flag<<endl;
        return flag;
    }
};

BETTER SOLUTION

使用两个递归，首先调用isSubStructure前序遍历树A的节点，然后调用judge判断以结点为根节点的子树是否包含树B。M为A节点数，N为B节点数，时间复杂度O(MN)，空间复杂度O(M)。

class Solution {
public:
    bool judge(TreeNode* a, TreeNode* b) {
        if(!b) {
            return true;
        }
        if(!a || a->val != b->val) {
            return false;
        }
        return judge(a->left, b->left) && judge(a->right, b->right);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!B || !A) {
            return false;
        }
        return judge(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
};

SUMMARY

树的相关问题考虑递归，设计递归时关注函数的功能、中止条件、返回值，不需要过于纠结运行细节。