python算法技巧——二叉树练习及掌握

叁歲伎倆 2023-09-29 12:44 25阅读 0赞

**目录**

1. 建立二叉树，同时使用中序(inorder)打印：

2. 使用前序(preorder)遍历打印二叉树：

3. 使用后序(postorder)遍历打印二叉树：

4. 计算二叉树的最大深度：

5. 计算二叉树的最小深度：

6. 将已排序数组转成二叉搜索树(binary search tree，BST)，并用中序打印：

7. 将未排序数组转成二叉搜索树(BST)，并用中序打印：

8. 求某个二叉树的路径数值和是否等于特定值：

9. 判断二叉树是否中心对称，或称为镜像(mirror)：

--------------------

#### **1. 建立二叉树，同时使用中序(inorder)打印：** ####

> 中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。
> 
> **遍历过程可以简写为：LDR；**

class treenode():
        def __init__(self, val=None):
            self.val = val
            self.left = None
            self.right = None
        
        def inorder(self):
        #中序打印
            if self.left:
            #如果左节点存在，递归调用下一层
                self.left.inorder()
            print(self.val)
            if self.right:
            #如果右节点存在，递归调用下一层
                self.right.inorder()
    
    def insertlist(data, root ,i ,n):
        if i<n:
            tmp = treenode(data[i])
            root = tmp
            root.left = insertlist(data, root.left, 2*i+1, n)
            root.right = insertlist(data, root.right, 2*i+2, n)
        return root
    
    tree = treenode()
    datas = [0, 1, 2, 3, 4, 5]
    n = len(datas)
    tree = insertlist(datas, tree, 0, n)
    tree.inorder()

**代码解析：**

> 上述的insertlist()函数是一个递归函数，这个这个程序的关键，这个函数所传递的参数有四个：
> 
>  *  data：要建立的二叉树列表；
>  *  root：目前的二叉树的根节点；
>  *  i：要建立的二叉树节点的列表数据索引；
>  *  n：列表数据的长度；
> 
> 其实递归调用在程序内部就是一个堆栈调用，这里我就不展开说明了。

--------------------

#### **2. 使用前序(preorder)遍历打印二叉树：** ####

> 前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根节点，然后遍历左子树，最后遍历右子树。
> 
>  **遍历过程可以简写为：DLR；**

# 使用前序(preorder)遍历打印二叉树-------------------------------------------------------------
    class treenode():
        def __init__(self, val=None):
            self.val = val
            self.left = None
            self.right =None
        
        def insert(self, val):
            if self.val:
                if val < self.val:
                    if self.left:
                        self.left.insert(val)
                    else:
                        self.left = treenode(val)
                else:
                    if self.right:
                        self.right.insert(val)
                    else:
                        self.right = treenode(val)
            else:
                self.val = val
    
        def preorder(self):
            print(self.val)
            if self.left:
                self.left.preorder()
            if self.right:
                self.right.preorder()
    
    tree = treenode()
    datas = [10, 21, 5, 9, 13, 28]
    for d in datas:
        tree.insert(d)
    tree.preorder()

--------------------

#### **3. 使用后序(postorder)遍历打印二叉树：** ####

> 后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。
> 
>  **遍历过程可以简写为：LRD；**

class treenode():
        def __init__(self, val=None):
            self.val = val
            self.left = None
            self.right =None
        
        def insert(self, val):
            if self.val:
                if val < self.val:
                    if self.left:
                        self.left.insert(val)
                    else:
                        self.left = treenode(val)
                else:
                    if self.right:
                        self.right.insert(val)
                    else:
                        self.right = treenode(val)
            else:
                self.val = val
    
        def postorder(self):
            if self.left:
                self.left.postorder()
            if self.right:
                self.right.postorder()
            print(self.val)
    
    tree = treenode()
    datas = [10, 21, 5, 9, 13, 28]
    for d in datas:
        tree.insert(d)
    tree.postorder()

--------------------

#### **4. 计算二叉树的最大深度：** ####

#计算二叉树的最大深度-------------------------------------------------------------
    class treenode():
        def __init__(self, val=None):
            self.val = val
            self.left = None
            self.right =None
    
    def insertlist(data, root, i, n):
        if i<n:
            tmp = treenode(data[i])
            root = tmp
            root.left = insertlist(data, root.left, 2*i+1, n)
            root.right = insertlist(data, root.right, 2*i+2, n)
        return root
    
    def maxdepth(root):
        if root == None:
            return 0
        else:
            return 1+max(maxdepth(root.left),maxdepth(root.right))
    
    tree = treenode()
    datas = [3, None, 20, 18, None, None, 7]
    n = len(datas)
    tree = insertlist(datas, tree, 0, n)
    print(maxdepth(tree))

--------------------

#### **5. 计算二叉树的最小深度：**  ####

#计算二叉树的最小深度-------------------------------------------------------------
    class treenode():
        def __init__(self, val=None):
            self.val = val
            self.left = None
            self.right =None
    
    def insertlist(data, root, i, n):
        if i<n:
            tmp = treenode(data[i])
            root = tmp
            root.left = insertlist(data, root.left, 2*i+1, n)
            root.right = insertlist(data, root.right, 2*i+2, n)
        return root
    
    def mindepth(root):
        if root == None:
            return 0
        if root.left != None and root.right == None:
            return mindepth(root.left)+1
        if root.left == None and root.right != None:
            return mindepth(root.right)+1
        return min(mindepth(root.left),mindepth(root.right))+1
    
    tree = treenode()
    datas = [6, 1, 4, 3, 7]
    n = len(datas)
    tree = insertlist(datas, tree, 0, n)
    print(mindepth(tree))

--------------------

#### **6. 将已排序数组转成二叉搜索树(binary search tree，BST)，并用中序打印：** ####

> **二叉搜索树：**即所有的左子树的值皆小于根节点的值，所有右节点的值皆大于根节点的值；

class treenode():
        def __init__(self, val=None):
            self.val = val
            self.left = None
            self.right = None
        
        def inorder(self):
            if self.left:
                self.left.inorder()
            print(self.val)
            if self.right:
                self.right.inorder()
    
    def sortedarraytobst(nums):
        if not nums:
            return None
        mid = len(nums)//2
        root = treenode(nums[mid])
    
        root.left = sortedarraytobst(nums[:mid])
        root.right = sortedarraytobst(nums[mid+1:])
        return root
    
    data = [-10, -3, 0, 5, 9]
    bst = sortedarraytobst(data)
    bst.inorder()

--------------------

#### **7. 将未排序数组转成二叉搜索树(BST)，并用中序打印：** ####

#将未排序数组转成二叉搜索树-------------------------------------------------------------
    class treenode():
        def __init__(self, val=None):
            self.val = val
            self.left = None
            self.right = None
        
        def insert(self, val):
            if self.val:
                if val < self.val:
                    if self.left:
                        self.left.insert(val)
                    else:
                        self.left = treenode(val)
                else:
                    if self.right:
                        self.right.insert(val)
                    else:
                        self.right = treenode(val)
            else:
                self.val = val
    
        def arraytobst(self, nums):
            root = treenode()
            for n in nums:
                root.insert(n)
            return root
    
        def inorder(self):
            if self.left:
                self.left.inorder()
            print(self.val)
            if self.right:
                self.right.inorder()
    
    tree = treenode()
    datas = [10, 21, 5, 9, 13, 28]
    tree = tree.arraytobst(datas)
    tree.inorder()

--------------------

#### **8. 求某个二叉树的路径数值和是否等于特定值：** ####

class treenode():
        def __init__(self, val=None):
            self.val = val
            self.left = None
            self.right =None
    
    def insertlist(data, root, i, n):
        if i<n:
            tmp = treenode(data[i])
            root = tmp
            root.left = insertlist(data, root.left, 2*i+1, n)
            root.right = insertlist(data, root.right, 2*i+2, n)
        return root
    
    def haspathsum(root, sum):
        if not root:
            return False
        if not root.left and not root.right:
            return root.val == sum
        return haspathsum(root.left, sum-root.val) or haspathsum(root.right, sum-root.val)
    
    tree =treenode()
    data = [5, 4, 9, 11, None, 13, 6, 7, 2]
    n = len(data)
    tree = insertlist(data, tree, 0, n)
    print(haspathsum(tree, 22))

**代码解析：**

> 这个程序的基本概念是，如果底下有子节点，sum就减去此节点值，进入递归；如果没有子节点，则比较目前节点值是不是等于最后sum的值，然后回传逻辑值。

--------------------

#### **9. 判断二叉树是否中心对称，或称为镜像(mirror)：** ####

#判断二叉树是否中心对称，或称为镜像(mirror)-----------------------------
    class treenode():
        def __init__(self, val=None):
            self.val = val
            self.left = None
            self.right =None
    
    def insertlist(data, root, i, n):
        if i<n:
            tmp = treenode(data[i])
            root = tmp
            root.left = insertlist(data, root.left, 2*i+1, n)
            root.right = insertlist(data, root.right, 2*i+2, n)
        return root
    
    def ismirroer(left, right):
        if left is None and right is None:
            return True
        if left is None or right is None:
            return False
        if left.val == right.val:
            outside = ismirroer(left.left, right.right)
            inside = ismirroer(left.right, right.left)
            return outside and inside
        return False
    
    def issymmetric(root):
        if root:
            return ismirroer(root.left, root.right)
        else:
            return True
    
    tree = treenode()
    data = [1, 2, 2, 3, 5, 5,3]
    n = len(data)
    tree = insertlist(data, tree, 0, n)
    print(issymmetric(tree))

--------------------

## **算法技巧专栏**  ##

[https://blog.csdn.net/weixin\_53919192/category\_11761989.html![icon-default.png_t_M3K6][]https://blog.csdn.net/weixin\_53919192/category\_11761989.html][https_blog.csdn.net_weixin_53919192_category_11761989.html_icon-default.png_t_M3K6_https_blog.csdn.net_weixin_53919192_category_11761989.html]

[icon-default.png_t_M3K6]: https://csdnimg.cn/release/blog_editor_html/release2.1.0/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=M3K6
[https_blog.csdn.net_weixin_53919192_category_11761989.html_icon-default.png_t_M3K6_https_blog.csdn.net_weixin_53919192_category_11761989.html]: https://blog.csdn.net/weixin_53919192/category_11761989.html