首页 > 其他分享 >从数组创建二叉树-Leetcode测试用

从数组创建二叉树-Leetcode测试用

时间:2024-04-07 15:13:43浏览次数:27  
标签:__ self 二叉树 数组 ind root Leetcode

Leetcode里和二叉树相关的题目,都是用一个数组表示二叉树的,而这个数组是按照层次优先顺序给出的,连其中的空结点也表示了出来,刚好就是2^N-1个结点,N表示层数。

但数组毕竟无法和二叉树一样具有链式结构,无法进行算法测试,因此尝试直接通过这样的数组构建二叉树。

通过数组创建这样的二叉树,也通过层次优先构建。和遍历一样,都利用队列结构去迭代。

from collections import deque


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def __eq__(self, other):
        return self.val == other.val

    def __str__(self):
        return str(self.val)

def build_bitree_fromarray(root_array):
    root_node = None
    if len(root_array) > 0:
        root_node = TreeNode(root_array[0])
    ind = 0
    dq = deque()
    dq.append(root_node)
    while len(dq) > 0:
        pre_node = dq.popleft()
        # print(f"{ind} -> ({(ind << 1) + 1}, {(ind << 1) + 2}) :: {root_array[ind]} -> ({root_array[(ind << 1) + 1]}, {root_array[(ind << 1) + 2]})")
        if (ind << 1) + 1 < len(root_array):
            if root_array[(ind << 1) + 1] != -1:
                tmp_node = TreeNode(root_array[(ind << 1) + 1])
                dq.append(tmp_node)
                pre_node.left = tmp_node
        if (ind << 1) + 2 < len(root_array):
            if root_array[(ind << 1) + 2] != -1:
                tmp_node = TreeNode(root_array[(ind << 1) + 2])
                dq.append(tmp_node)
                pre_node.right = tmp_node
        ind += 1
    return root_node


if __name__ == '__main__':
    root = [3, 5, 1, 6, 2, 0, 8, -1, -1, 7, 4]
    root_node = build_bitree_fromarray(root_array=root)
    print_tree_level(root_node)

打印也可以通过层次优先打印,要在创建的时候标记每一个结点的层数。

标签:__,self,二叉树,数组,ind,root,Leetcode
From: https://www.cnblogs.com/zhaoke271828/p/18119092

相关文章

  • LeetCode 面试经典150题---002
    ###169.多数元素给定一个大小为n的数组nums,返回其中的多数元素。多数元素是指在数组中出现次数大于⌊n/2⌋的元素。你可以假设数组是非空的,并且给定的数组总是存在多数元素。n==nums.length1<=n<=5*104-109<=nums[i]<=109这题可太有意思了,意思就是找......
  • 二叉树-统一迭代法
    迭代法实现的前中后序遍历,除了前序和后序相互关联,中序则是另一种风格。我们需要针对三种遍历方式实现统一风格的代码。如何统一风格:解决访问节点(遍历节点)和处理节点(将元素放进结果集)不一致的情况。将访问的节点放入栈中,把要处理的节点放入栈中但是做标记(紧接着放入一个空指针)......
  • 18天【代码随想录算法训练营34期】● 513.找树左下角的值 ● 112. 路径总和 113.路径
    513.找树左下角的值#Definitionforabinarytreenode.#classTreeNode:#def__init__(self,val=0,left=None,right=None):#self.val=val#self.left=left#self.right=rightclassSolution:deffindBottomLeftValue(self......
  • LeetCode 2468. Split Message Based on Limit
    原题链接在这里:https://leetcode.com/problems/split-message-based-on-limit/description/题目:Youaregivenastring, message,andapositiveinteger, limit.Youmust split message intooneormore parts basedon limit.Eachresultingpartshouldhaveth......
  • 二叉树-迭代遍历
    递归的实现是每次递归调用都把函数的局部变量、参数值和返回地址等压入调用栈中,然后递归返回的时候就从栈顶弹出上一次递归的各项参数。可利用栈实现二叉树的前中后序遍历。前序遍历前序遍历是中左右的顺序,整体过程就是逐次访问父节点,压入右孩子再压入左孩子,由于访问的节点和待......
  • LeetCode 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows
    原题链接在这里:https://leetcode.com/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/description/题目:Youaregivenan mxn matrix mat thathasitsrowssortedinnon-decreasingorderandaninteger k.Youareallowedtochoose exactlyo......
  • LeetCode 1891. Cutting Ribbons
    原题链接在这里:https://leetcode.com/problems/cutting-ribbons/description/题目:Youaregivenanintegerarray ribbons,where ribbons[i] representsthelengthofthe ith ribbon,andaninteger k.Youmaycutanyoftheribbonsintoanynumberofsegments......
  • JAVA入门——对象数组:对象数组进行增删改查
    题目:不使用数据库,定义长度为3的数组,存储1~3名学生对象作为初始值(即1名2名3名都可以),学生对象的学号具有唯一性。学生属性:学号,姓名,年龄。要求一:再添加一个学生对象,遍历所有学生要求二:通过学号删除学生信息,遍历所有学生要求三:通过学号查询学生信息,若存在则修改年龄,遍历所有......
  • 2.手写JavaScript广度和深度优先遍历二叉树
    一、核心思想:1.深度遍历:依靠栈先进后出的机制,分别设置返回结果的数组和栈数组,首先判断栈非空,对每个结点,将其出栈并把值push到结果数组,判断是否有右左孩子,分别将其加入栈中,循环执行上述操作。否则返回结果数组。2.广度遍历:依靠队列先进先出的机制,分别设置返回结果的数组和队......
  • LeetCode 面试经典150题---001
    少年听雨歌楼上,红烛昏罗帐。壮年听雨客舟中,江阔云低、断雁叫西风而今听雨僧庐下鬓已星星也。悲欢离合总无情,一任阶前、点滴到天明。###88.合并两个有序数组给你两个按非递减顺序排列的整数数组nums1和nums2,另有两个整数m和n,分别表示nums1和nums2中的......