题解 | #树的子结构#

1. 一直向左子树挨个节点搜索。进入递归看是否满足条件。如果满足，就返回true。
2. 在向左的时候要记住当前节点，因为待会还要向右遍历这个树。记入到stack中就好，因为可以倒着来遍历。
3. 之后每次该节点左走不了之后，弹栈，依次从后往前走当前节点的右节点，当然走右节点的时候，也是往左节点遍历。并把新的右节点压栈，来遍历以后的右节点的右节点。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:


    bool isSub(TreeNode* pRoot1, TreeNode* pRoot2){

        //base case -1
        if(!pRoot2) return true;
        //base case -2
        if(!pRoot1) return false;


        //三个条件取判断
        return pRoot1->val == pRoot2->val && isSub(pRoot1->left,pRoot2->left) && isSub(pRoot1->right, pRoot2->right);

    }


    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        if(!pRoot1||!pRoot2) return false;//ps：我们约定空树不是任意一个树的子结构

        stack<TreeNode*> st;//为了保存右结点

        while(pRoot1||!st.empty()){//同时也防止了空节点,同时也为了处理空节点
             while(pRoot1){//同时也防止了空节点
                if(pRoot1->val == pRoot2->val && isSub(pRoot1, pRoot2)) return true;
                 st.push(pRoot1);//为了之后向右
                 pRoot1 = pRoot1->left;//一直向左，然后验证是不是符合。
            }
            TreeNode* t = st.top();
            st.pop();
            pRoot1 = t->right;
        }
       //直接返回false
       return false;

    }
};