关于二叉树:一周刷完剑指offer17树的子结构

树的子结构

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 = None
class 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)

如果您感觉本文有用，请点个“在看”