二叉树介绍

需求 了解二叉树 解决 是什么 从根节点开始,小的向左边放,大的向右边放,一层一层放下去。满足左小右大原则。 没有子节点的是叶子 子节点的个数是度 从根到当前节点的为一路径上节点总数是深度 从当前节点到最远叶子路径上的节点总数是高度 用处 用于大数据量时的反复的搜索和插入。 有序链表: 查找成本大 O(N), 插入成本小 O(1) 有序数组: 查找成本小 O(1), 插入成本大 O(N) 排序二叉树: 比较折中,查找时类似于二分查找 O(logN), 插入成本也小 O(logN). 打印 层序遍历 public int[] levelOrder(TreeNode root) { int arr[]=new int[10000]; int index=0; Queue<TreeNode>queue=new ArrayDeque<>(); if(root!=null) queue.add(root); while (!queue.isEmpty()){ TreeNode node=queue.poll(); arr[index++]= node.val; if(node.left!=null) queue.add(node.left); if(node.right!=null) queue.add(node.right); } return Arrays.copyOf(arr,index); } 分层存储 public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>>list=new ArrayList<List<Integer>>(); if(root==null)return list; Queue<TreeNode>q1=new ArrayDeque<TreeNode>(); q1.add(root); while (!...

<span title='2023-08-16 10:20:00 +0800 CST'>2023-08-16</span>&nbsp;·&nbsp;3 min&nbsp;·&nbsp;565 words&nbsp;·&nbsp;RamLife