剑指offer--树的子结构

题目描述 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

---

Java AC代码：

代码语言：javascript复制

public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}

/*
 * 解题思路：俩颗树都不为空时，如果根节点相同
 * ，那么判断root2是不是root1的子树
 * 如果不是，那么判断root2是不是root1左子树的子树
 * 如果还不是，那么判断root2是不是root1右子树的子树
 * 如果还不是，返回root2不是root1的子树
 */

public class Solution {

    public boolean IsSubTree(TreeNode root1,TreeNode root2){
        /*
         * 判断root2是否为root1的子树
         */
        if ( root2 == null){
            return true;
        }else if ( root1 == null){
            return false;
        }

        if ( root1.val != root2.val){
            return false;
        }
        return IsSubTree(root1.left, root2.left)&&IsSubTree(root1.right, root2.right);
    }

    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        boolean result = false;
        if ( root1 != null && root2 != null){
            if ( root1.val == root2.val){
                result = IsSubTree(root1, root2);
            }
            if(!result){
                result = IsSubTree(root1.left, root2);
            }
            if (!result){
                result = IsSubTree(root1.right, root2);
            }
        }
        return result;
    }
}

---

C AC代码

代码语言：javascript复制

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
class Solution {
    public:
        bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2){
            if(pRoot2 == NULL){
                return false;
            }
            if(pRoot1 == NULL){
                return false;
            }
            return dfs(pRoot1,pRoot2) || HasSubtree(pRoot1->right,pRoot2) || HasSubtree(pRoot1->left,pRoot2);
        }

        bool dfs(TreeNode* pRoot1, TreeNode* pRoot2){
            if(pRoot2 == NULL){
                return true;
            }
            if(pRoot1 == NULL){
                return false;
            }
            if(pRoot1->val != pRoot2->val){
                return false;
            }
            return dfs(pRoot1->left,pRoot2->left) && dfs(pRoot1->right,pRoot2->right);
        }
};

java c++ 二叉树 ps

0 人点赞