剑指Offer第17题-树的子结构
2018-05-21 本文已影响0人
Joseph_Chu
题目
输入两棵二叉树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为例）
- &&的短路特性: 因为程序从左往右执行的，当判断左边为false时&&的返回结果就已经注定是false , 所以后面的判断计算机就不执行了
- || 的短路特性：因为程序是从左往右执行，当判断左边为true时 返回结果就已经注定是 true， 所以后面的判断计算机不执行
