[PYTHON] Programming to fight in the world-Chapter 4

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)
                

test I haven't made all four chapters. I'm making it, but it's just not listed (quivering voice) I'm not sure if the match tree is working properly

Recommended Posts

Programming to fight in the world-Chapter 4
Programming to fight in the world ~ 5-1
Programming to fight in the world ~ 5-5,5-6
Programming to fight in the world ~ 5-2
Activity record in the programming circle
"Book to train programming skills to fight in the world" Python code answer example --1.3 URLify
In the python command python points to python3.8
"Book to train programming skills to fight in the world" Python code answer example --2.6 palindrome
Cython to try in the shortest
"Book to train programming skills to fight in the world" Python code answer example --2.4 Splitting the list
"Book to train programming skills to fight in the world" Python code answer example --2.7 intersecting nodes
"A book to train programming skills to fight in the world" Python code answer example --1.8 "0" matrix
In Jupyter, add IPerl to the kernel.
Draw graphs in the programming language Julia
Various comments to write in the program
"A book to train programming skills to fight in the world" Python code Solution example --1.6 String compression
"A book to train programming skills to fight in the world" Python code solution example --1.5 One-shot conversion
"A book to train programming skills to fight in the world" Python code answer example --3.1 Three stacks
"A book to train programming skills to fight in the world" Python code Solution example --1.7 Matrix rotation
"Book to train programming skills to fight in the world" Python code answer example --1.4 Permutation of sentences
"A book to train programming skills to fight in the world" Python code Solution example --2.8 Loop detection
"Book to train programming skills to fight in the world" Python code solution example --- Removed elements between 2.3
"Book to train programming skills to fight in the world" Python code Solution example --2.1 Remove duplicate elements
Programming in python
"A book to train programming skills to fight in the world" Python code answer example --1.9 Rotation of strings
"A book to train programming skills to fight in the world" Python code answer example --1.1 Duplicate character string
Twitter streaming client to enjoy in the terminal
To dynamically replace the next method in python
Draw graphs in Julia ... Leave the graphs to Python
The trick to write flatten concisely in python
How to get the files in the [Python] folder
Use pygogo to get the log in json.
I want to display the progress in Python!
"A book to train programming skills to fight in the world" Python code answer example --2.2 Returns the Kth from the back
How to retrieve the nth largest value in Python
I tried to graph the packages installed in Python
How to get the variable name itself in python
Try to solve the programming challenge book with python3
How to run the Ansible module added in Ansible Tower
How to get the number of digits in Python
How to know the current directory in Python in Blender
"A book to train programming skills to fight in the world" Python code answer example --1.2 Count the number of the same characters
Convert the image in .zip to PDF with Python
Set the form DateField to type = date in Django
How to use the exists clause in Django's queryset
I want to write in Python! (3) Utilize the mock
The road to Pythonista
Python programming in Excel
How to use the model learned in Lobe in Python
Try to decipher the login data stored in Firefox
The easiest line bot in the world to lose weight
How to enjoy Python on Android !! Programming on the go !!
Do not pass self to ProcessPoolExecutor in the class
[Python] How to output the list values in order
Kaggle Tutorial Titanic know-how to be in the top 2%
The road to Djangoist
To do the equivalent of Ruby's ObjectSpace._id2ref in Python
The programming language you want to be able to use
The story around the time acquisition API in programming languages
I want to use the R dataset in python
Python OpenCV tried to display the image in text.