剑指Offer第17题-树的子结构

题目

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

思路

什么是二叉树的子结构及子树？

• 子树的意思是包含了一个结点，就得包含这个结点下的所有节点，一棵大小为n的二叉树有n个子树，就是分别以每个结点为根的子树。
• 子结构的意思是包含了一个结点，可以只取左子树或者右子树，或者都不取。

基本思想是递归
我们首先判断A, B是否为空，若有任何一个为空，则直接返回False。
然后判断A, B两个节点的值是否相同，如果不相同，就可以直接返回False。
如果相同，再判断A的左子树和B的左子树，A的右子树和B的右子树是否有相同的值，若B没有对应的子树就可以直接返回True。

代码

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def is_subtree(self, pRoot1, pRoot2):
        if not pRoot2: return True
        if not pRoot1: return False
        if pRoot1.val == pRoot2.val:
            return self.is_subtree(pRoot1.left, pRoot2.left) and \
                   self.is_subtree(pRoot1.right, pRoot2.right)
        else: return False
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if (not pRoot1) or (not pRoot2): return False
        return self.is_subtree(pRoot1, pRoot2) or \
               self.HasSubtree(pRoot1.left, pRoot2) or \
               self.HasSubtree(pRoot1.right, pRoot2)

代码翻译自牛客网某大牛的C++代码
用到了 短路特性 这一技巧

• 逻辑运算符的短路特性（以java为例）

1. &&的短路特性: 因为程序从左往右执行的，当判断左边为false时&&的返回结果就已经注定是false , 所以后面的判断计算机就不执行了
2. || 的短路特性：因为程序是从左往右执行，当判断左边为true时 返回结果就已经注定是 true， 所以后面的判断计算机不执行

参考

• https://www.nowcoder.com/questionTerminal/6e196c44c7004d15b1610b9afca8bd88
• https://blog.csdn.net/nepenthe_csdn/article/details/52348194