剑指offer--algorithm8

今天的两道题主要侧重于树的结构，树相对于链表来说指针更多，因此难度会更大点，需要好好掌握

题16--树的子结构

输入两棵树A,B,判断B是不是A的子结构，其中空树不是任意树的子结构

关于本题的思路就是找A中与B中相同的节点，思路如下：

image.png
image.png
image.png
本题的关键在于递归的使用，以及树的构建（与链表类似）

下面为代码和注释部分

class tree(object):
    def __init__(self,value):
        self.value=value
        self.left=None
        self.right=None#这个与链表一样，类似于设定两个指针
        
        

class solution(object):
    def result_decision(self,ptree1,ptree2):
        result=False#首先建立flag 
        if ptree1!=None and ptree2!=None:#当确定两者都不为空的时候
            if ptree1.value==ptree2.value:#当两个树的根节点就相同
                result=self.subtree(ptree1,ptree2)
            if not result:
                self.result_decision(ptree1.left,ptree2)#当没有检测到节点相等的时候，那么就继续遍历大树1与小树2的节点进行比较
            if not result:
                self.result_decision(ptree1.right,ptree2)#当没有检测到节点相等的时候，那么就继续遍历大树1与小树2的节点进行比较
        return result 
    def subtree(self,ptree1,ptree2):
        if ptree2==None:
            return True#当树2遍历结束后，说明树2肯定为树1的子树，所以返回True
        if ptree1==None:#当树1遍历结束后，此时说明，肯定树2不为树1的子树，所以返回False,这两个If语句不能相反
            return False
        if ptree1.value!=ptree2.value:
            return False 
        
        return self.subtree(ptree1.left,ptree2.left) and self.subtree(ptree1.right,ptree2.right)
    
    
    
    
def main():
    ptree1=tree(8)
    ptree2=tree(8)
    ptree3=tree(7)
    ptree4=tree(9)
    ptree5=tree(2)
    ptree6=tree(4)
    ptree7=tree(7)
    ptree1.left=ptree2
    ptree1.right=ptree3
    ptree2.left=ptree4
    ptree2.right=ptree5
    ptree5.left=ptree6
    ptree5.right=ptree7
    
    
    ptree8=tree(8)
    ptree9=tree(9)
    ptree10=tree(2)
    ptree8.left=ptree9
    ptree8.right=ptree10
    s=solution()
    print (s.result_decision(ptree1,ptree8))
    
    
if __name__=='__main__':
    main()

题17--二叉树镜像

输入一个二叉树，然后输出该二叉树的镜像

首先要了解一下树的镜像概念

image.png

那么如何的一种交换思路呢？

image.png

该思路的描述是

image.png
下面为代码和解释部分

class tree(object):
    def __init__(self,value):
        self.value=value
        self.left=None 
        self.right=None 
        


class solution(object):
    def mirror(self,root):
        if root==None:
            return 
        if root.left==None and root.right==None:
            return root 
        ptemp=root.left 
        root.left=root.right 
        root.right=ptemp 
        
        self.mirror(root.left)
        self.mirror(root.right)
   
            
            
def main():
    node1=tree(8)
    node2=tree(6)
    node3=tree(10)
    node4=tree(5)
    node5=tree(7)
    node6=tree(9)
    node7=tree(11)
    
    node1.left=node2
    node1.right=node3
    node2.left=node4
    node2.right=node5
    node3.left=node6
    node3.right=node7
    s=solution()
    print (s.mirror(node1))
    
    
    
if __name__=='__main__':
    main()