树Tree

节点类

class Node(object):
    def __init__(self,data=None):
        self.val = data
        self.left = None 
        self.right = None 

二叉树前、中、后、按层遍历

class MyTree(object):
    def __init__(self):
        self.root = Node()
    def add(self,data):
        if self.root.val is None:
            self.root.val = data
            return self.root
        tempList = []
        tempList.append(self.root)
        while len(tempList):
            curNode = tempList.pop(0)
            if curNode.left is None:
                curNode.left = Node(data)
                return self.root
            if curNode.right is None:
                curNode.right = Node(data)
                return self.root
            tempList.append(curNode.left)
            tempList.append(curNode.right)

    def per_order_recurise(self,node):
        if node is None:
            return
        print(node.val)
        self.per_order_recurise(node.left)
        self.per_order_recurise(node.right)

    def per_order_stack(self,node):
        if node is None:
            return
        stack = []
        nodeTemp = node
        while nodeTemp or len(stack):
            while nodeTemp:
                print(nodeTemp.val)
                stack.append(nodeTemp)
                nodeTemp = nodeTemp.left
            nodeTemp = stack.pop(0)
            if nodeTemp:
                nodeTemp = nodeTemp.right

    def in_order_recurise(self,node):
        if node is None:
            return
        self.in_order_recurise(node.left)
        print(node.val)
        self.in_order_recurise(node.right)
    
    def post_order_recurise(self,node):
        if node is None:
            return
        self.post_order_recurise(node.left)
        self.post_order_recurise(node.right)
        print(node.val)

    def level_recursion(self,node):
        if node is None:
            return 
        tempList = []
        tempList.append(node)
        tempNode = node
        count = 0
        while len(tempList):
            curNode = tempList.pop(0)
            if curNode:
                print(curNode.val)
            if curNode==tempNode:
                count += 1
                tempNode = curNode.right
                print('level :',count)
            if curNode.left is None:
                continue 
            tempList.append(curNode.left)
            if curNode.right is None:
                continue 
            tempList.append(curNode.right)

二叉搜索树

class SearchTree():
    def __init__(self):
        self.root = None
        
    def insert(self, root, val):
        '''二叉搜索树插入操作'''
        if root == None:
            root = TreeNode(val)
        elif val < root.val:
            root.left = self.insert(root.left, val)
        elif val > root.val:
            root.right = self.insert(root.right, val)
        return root

    def query(self, root, val):
        '''二叉搜索树查询操作'''
        if root == None:
            return False
        if root.val == val:
            return True
        elif val < root.val:
            return self.query(root.left, val)
        elif val > root.val:
            return self.query(root.right, val)

    def findMin(self, root):
        '''查找二叉搜索树中最小值点'''
        if root.left:
            return self.findMin(root.left)
        else:
            return root

最大、最小深度

class Solution:
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root==None:
            return 0
        if root.left==None or root.right==None:
            return 1+ self.maxDepth(root.left)+self.maxDepth(root.right)
        return 1+ max(self.maxDepth(root.left),self.maxDepth(root.right))

class Solution(object):
    def minDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        if root.left is None or root.right is None:
            return 1 + min(self.minDepth(root.left)+self.minDepth(root.right))
            # 只有叶子节点才能用于计算深度，为空不是在叶子，不能用于计算深度。
            # 不知道那个为空，所以都加上，反正为0.
        else:
            return 1  + min(self.minDepth(root.left),self.minDepth(root.right))

# 层遍历
# 建立一个空列表，待遍历 temp_list，建立一个标记节点temp_node
# 将树的根节点放入temp_list，temp_node=root
# while temp_list 不为空，弹出list的0位节点，打印节点值，并将该节点的子节点加入（append）temp_list中。
# 如果弹出节点==temp_node,则层数加一，并将temp_list最后的节点赋值给temp_node

# 非递归的先、中、后序遍历
# 建立一个待遍历temp_list，将根节点放入
# while temp_list 不为空，弹出0位置节点，打印值，将子节点append到temp_list中。

# 递归建二叉搜索树的过程
# 传入根节点，无节点建立节点
# 有节点，比较值，小于则将左节点作为根节点，递归
# 大于则将右节点作为根节点，递归
# 搜索过程
# 与根节点比较，如果小于则递归查找左侧，如果大于则递归查找右侧，直到找到或者，没找到。可以返回最近的叶子节点。