美文网首页
树的简单算法题

树的简单算法题

作者: davidic | 来源:发表于2019-03-04 17:56 被阅读0次

    二叉树插入

    class TreeNode:
        def __init__(self, val, left, right):
            self.val = val
            self.left = left
            self.right = right
          
    class BinarySearchTree:
        def insert(self, root, val):
            if root == None:
                root = TreeNode(val, None, None)
            else:
                if val < root.val:
                    root.left = self.insert(root.left, val)
                if val > root.val:
                    root.right = self.insert(root.right, val)
            return root    
    
        def preOrder(self, root):
            if root:
                print root.val
                self.preOrder(root.left)
                self.preOrder(root.right)
    
    Tree = BinarySearchTree()
    root = None
    for i in [1,2,3]:
        root = Tree.insert(root, i)
    Tree.preOrder(root)
    

    有序数组创建二叉树

    class Solution:  
        def sortedArrayToBST(self, num):  
            if not num:  
                return None  
              
            mid = len(num)//2  #“//”表示整数除法;“/”浮点数除法;  
            root = TreeNode(num[mid])  
            left = num[:mid]  
            right = num[mid+1:]  
            root.left = self.sortedArrayToBST(left)  
            root.right = self.sortedArrayToBST(right)  
            return root  
    

    遍历二叉树

    algorithms/

    前序 根左右

    中序 左根右

    后序 左右根

    递归方式

    class Tree(object):
        def __init__(self,data,left,right):
            self.data=data
            self.left=left
            self.right=right
    def post_visit(Tree):
        if Tree:
            post_visit(Tree.left)
            post_visit(Tree.right)
            print Tree.data
    def pre_visit(Tree):
        if Tree:
            print Tree.data
            pre_visit(Tree.left)
            pre_visit(Tree.right)
    def in_visit(Tree):
        if Tree:
            in_visit(Tree.left)
            print Tree.data
            in_visit(Tree.right)
    

    非递归

    class TreeNode:  
        def __init__(self,value=None,leftNode=None,rightNode=None):  
            self.value = value  
            self.leftNode = leftNode  
            self.rightNode = rightNode  
      
      
    class Tree:  
        def __init__(self,root=None):  
            self.root = root  
      
        def preOrder(self):  
            if not self.root:  
                return  
            stackNode = []  
            stackNode.append(self.root)  
            while stackNode:  
                node = stackNode.pop()  
                print node.value,  
                if node.rightNode:  
                    stackNode.append(node.rightNode)  
                if node.leftNode:  
                    stackNode.append(node.leftNode)  
    

    平衡二叉树

    输入一棵二叉树,判断该二叉树是否是平衡二叉树。

    class Solution:
        def getDepth(self , Root):
            if Root == None:
                return 0;
            lDepth = self.getDepth(Root.left);
            rDepth = self.getDepth(Root.right);
            return max(lDepth , rDepth) + 1;
    
        def IsBalanced_Solution(self, pRoot):
            if not pRoot:
                return True
            lDepth = self.getDepth(pRoot.left);
            rDepth = self.getDepth(pRoot.right);
            diff = lDepth - rDepth;
            if diff < -1 or diff > 1:
                return False;
            return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right);
    

    判断一棵树是否为另一棵的子树

    给定两棵二叉树,判断T2是否是T1某棵子数的结构。

    T1序列化成字符串str1;

    T2序列化成字符串str2;

    用KMP算法判断str1中是否包含str2:如果str1包含str2,说明T1包含于T2结构一致的子树。

    KMP算法

    #KMP  
    def kmp_match(s, p):  
        m = len(s); n = len(p)  
        cur = 0#起始指针cur  
        table = partial_table(p)  
        while cur<=m-n:  
            for i in range(n):  
                if s[i+cur]!=p[i]:  
                    cur += max(i - table[i-1], 1)#有了部分匹配表,我们不只是单纯的1位1位往右移,可以一次移动多位  
                    break  
            else:  
                return True  
        return False  
      
    #部分匹配表  
    def partial_table(p):  
        '''''partial_table("ABCDABD") -> [0, 0, 0, 0, 1, 2, 0]'''  
        prefix = set()  
        postfix = set()  
        ret = [0]  
        for i in range(1,len(p)):  
            prefix.add(p[:i])  
            postfix = {p[j:i+1] for j in range(1,i+1)}  
            ret.append(len((prefix&postfix or {''}).pop()))  
        return ret  
    

    相关文章

      网友评论

          本文标题:树的简单算法题

          本文链接:https://www.haomeiwen.com/subject/pcziuqtx.html