题解 | #树的子结构#

树的子结构

http://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88

  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;

    }
};
剑指Offer 文章被收录于专栏

剑指offer的解析结合

全部评论

相关推荐

07-03 16:02
门头沟学院 Java
点赞 评论 收藏
分享
05-20 21:57
已编辑
门头沟学院 Java
喜欢吃卤蛋的悲伤蛙在...:建信融通没消息吧,我2说有实习挂简历不理了
点赞 评论 收藏
分享
05-12 11:09
已编辑
门头沟学院 后端
已注销:没必要放这么多专业技能的描述。这些应该是默认已会的,写这么多行感觉在凑内容。项目这块感觉再包装包装吧,换个名字,虽然大家的项目基本都是网上套壳的,但是你这也太明显了。放一个业务项目,再放一个技术项目。技术项目,例如中间件的一些扩展和尝试。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务