世界で戦うプログラミング〜第４章

```python:tree.py

# -*- coding:utf-8 -*-
import math

    
class TreeNode:
    def __init__(self,data=None,left=None,right=None):
        self.data = data
        self.left = left
        self.right = right
        self.adjacent = [self.left,self.right]
        self.visited = False
        self.next =None
        

class Treeutils:
    def __init__(self):
        self.classes = 0
    def treeappend(self,node,x):
        if node == None:
            return TreeNode(x)
        elif x == node.data:
            return node
        elif x < node.data:
            node.left = self.treeappend(node.left,x)
        else:
            node.right = self.treeappend(node.right,x)
            
        return node
        

    def treecheck(self,node):
        if node == None:
            return 0
        leftheight = self.treecheck(node.left)
        if leftheight == -1:
            return -1
        
        rightheight = self.treecheck(node.right)
        if rightheight == -1:
            return -1
        
        heightdiff = leftheight - rightheight
        
        if math.fabs(heightdiff) > 1:
            return -1
        else:
            return max(leftheight,rightheight) + 1
        
    def isBalanced(self,node):
        if self.treecheck(node) == -1:
            return None
        else:
            return True
        
    def createMinBST(self,arr =[],start = 0,end = 0):
        if end < start:
            return None
        mid = (start + end) / 2
        
        n = TreeNode(arr[int(mid)])
        n.left = self.createMinBST(arr,start,mid -1)
        n.right = self.createMinBST(arr,mid+1,end)
        return n
    
    def create(self,x):
        return self.createMinBST(range(x),0,len(range(x))-1)
    
    def covers(self,root,p):
        if root == None:
            return False
        if root == p:
            return True
        return self.covers(root.left,p) or self.covers(root.right,p)
    
    def commonAncestorHelper(self,root,p,q):
        if root == None:
            return None
        if root == p or root == q:
            return root
        is_p_on_left = self.covers(root.left,p)
        is_q_on_right = self.covers(root.right,q)
        
        if is_p_on_left != is_q_on_right:
            return root
        
        child = is_p_on_left if root.left else root.right
        
        return self.commonAncestorHelper(child,p,q)
    
    def commonAncestor(self,root,p,q):
        if self.covers(root,p) != True or self.covers(root,q) != True:
            return None
        return self.commonAncestorHelper(root,p,q)
            
        
    def containsTree(self,node1,node2):
        if node2 == None:return True
        return self.subTree(node1,node2)
    
    def subTree(self,node1,node2):
        if node1 == None:
            return False
        
        if node1.data ==node2.data:
            if self.matchTree(node1,node2):
                return True
        
        return self.subTree(node1.left,node2) or self.subTree(node1.right,node2)
    
    def matchTree(self,node1,node2):
        if node1 == None and node2 == None:
            return True
        
        if node1 or node2 == None:return False
        
        if node1.data != node2.data:return False
        
        return self.matchTree(node1.left,node2.left) and self.matchTree(node1.right,node2.right)
                
```

テスト
４章全部は作っていない.
作っているけど載っけてないだけ(震え声)
match tree　はちゃんと動いているかいまいちわかりません