如何用层序遍历一个普通的二叉树,并把它以完全二叉树的形式存入数组内呢?为空的地方存入null这种思路,想了半天都没法实现,
2条回答 默认 最新
- _Mr.Tree 2021-11-22 20:59关注
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; public class Test { static class TreeNode{ TreeNode left; TreeNode right; int val; public TreeNode(TreeNode left, TreeNode right, int val) { this.left = left; this.right = right; this.val = val; } } public static void main(String[] args) { TreeNode seven = new TreeNode(null, null, 7); TreeNode eight = new TreeNode(null, null, 8); TreeNode four = new TreeNode(seven, eight, 4); TreeNode nine = new TreeNode(null, null, 9); TreeNode ten = new TreeNode(null, null, 10); TreeNode five = new TreeNode(nine, ten, 5); TreeNode two = new TreeNode(four, five, 2); TreeNode eleven = new TreeNode(null, null, 11); TreeNode twelve = new TreeNode(null, null, 12); TreeNode six = new TreeNode(eleven, twelve, 6); TreeNode three = new TreeNode(null, six, 3); TreeNode one = new TreeNode(two, three, 1); levelTraver(one).forEach(e -> System.out.print((e == null ? "null" : e.val) + " ")); } private static List<TreeNode> levelTraver(TreeNode root){ List<TreeNode> resultList = new ArrayList<>(); if(root == null) return resultList; Queue<TreeNode> q = new LinkedList<>(); boolean hasChild = false; q.offer(root); if(root.left != null || root.right != null) hasChild = true; while(!q.isEmpty()){ int len = q.size(); boolean isAllNull = true; boolean nextHasChild = false; for(int i = 0; i < len; i++){ resultList.add((root = q.poll())); if(root == null){ if(hasChild){ q.offer(null); q.offer(null); } continue; } isAllNull = false; if(root.left != null){ q.offer(root.left); nextHasChild = true; }else if(hasChild){ q.offer(null); } if(root.right != null){ q.offer(root.right); nextHasChild = true; }else if(hasChild){ q.offer(null); } } hasChild = nextHasChild; if(isAllNull){ while(len-- > 0){ resultList.remove(resultList.size() - 1); } break; } } return resultList; } }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 1无用
悬赏问题
- ¥500 52810做蓝牙接受端
- ¥15 基于PLC的三轴机械手程序
- ¥15 多址通信方式的抗噪声性能和系统容量对比
- ¥15 winform的chart曲线生成时有凸起
- ¥15 msix packaging tool打包问题
- ¥15 finalshell节点的搭建代码和那个端口代码教程
- ¥15 Centos / PETSc / PETGEM
- ¥15 centos7.9 IPv6端口telnet和端口监控问题
- ¥20 完全没有学习过GAN,看了CSDN的一篇文章,里面有代码但是完全不知道如何操作
- ¥15 使用ue5插件narrative时如何切换关卡也保存叙事任务记录