树的子结构

1. 题目形容

输出两棵二叉树A，B，判断B是不是A的子结构。（ps：咱们约定空树不是任意一个树的子结构）

2. 示例

无

3. 解题思路

波及树结构的题目，个别都应用递归办法

  1. 如果两棵二叉树 节点值不雷同：

    1-1： 递归遍历 A树左子树

    1-2： 递归遍历 A 树右子树

  2. 如果两棵二叉树 节点值雷同：

    1-1：B树为空，则B是A的子树

    1-2： 递归判断AB树节点值是否雷同

4. Java实现

/**public class TreeNode {    int val = 0;    TreeNode left = null;    TreeNode right = null;    public TreeNode(int val) {        this.val = val;    }}*/public class Solution {    public boolean HasSubtree(TreeNode root1,TreeNode root2) {        boolean res = false;                if (root1 != null && root2 != null){            if (root1.val == root2.val){                res = doseSubtree(root1, root2);        }        if (res == false){            res = HasSubtree(root1.left, root2);        }        if (res == false){            res = HasSubtree(root1.right, root2);        }    }        return res;    }    private boolean doseSubtree(TreeNode root1,TreeNode root2){        if (root2 == null){            return true;        }        if (root1 == null){            return false;        }        if (root1.val != root2.val){            return false;        }        return doseSubtree(root1.left, root2.left) && doseSubtree(root1.right, root2.right);            }  }

5. Python实现

# -*- coding:utf-8 -*-# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def HasSubtree(self, pRoot1, pRoot2):        # write code here        result = False         if pRoot1 and pRoot2: #如果两颗树结点都不为空            if pRoot1.val == pRoot2.val:# 如果结点的值雷同的话                result = self.DoseSubtree(pRoot1, pRoot2)            if not result: # 不雷同，则判断tree1 左子树结构                result = self.HasSubtree(pRoot1.left, pRoot2)            if not result:                result = self.HasSubtree(pRoot1.right, pRoot2)        return result                    def DoseSubtree(self, pRoot1, pRoot2):        if not pRoot2: #如果tree2 树为空的话，阐明就是子树            return True         if not pRoot1:            return False        if pRoot1.val != pRoot2.val:            return False        # 持续判断1,2左子树和1,2右子树        return self.DoseSubtree(pRoot1.left, pRoot2.left) and self.DoseSubtree(pRoot1.right, pRoot2.right)
如果您感觉本文有用，请点个“在看”