- ， 31 7月 2022
- 作者 847954981@qq.com
- 我的编程之路, 算法学习
二叉树同层处理
个人整理，非最优解
二叉树算法中，如果我们需要如：获取每一层二叉树的元素总和时，这样对二叉树每一层进行分开计算，可以使用队列加两层while循环：
代码语言：javascript复制public void aSum(TreeNode root) {
int floor=0;
Deque<TreeNode> queue = new ArrayDeque<>(); //队列
queue.offer(root); //初始根节点压入队列
while(!queue.isEmpty()){ //第一层while,知道二叉树被遍历完全
floor ; //表示现在正在计算的层数
int size=queue.size(); //通过获取此时的size来表示该层有多少元素
int sum=0;
while(size!=0){ //第二层while,通过size来遍历同层的元素
size--; //每遍历一个同层元素减1
TreeNode ls=queue.pop(); //将元素出队列
sum =ls.val;
if(ls.left!=null){queue.offer(ls.left);} //左分支加入队列
if(ls.right!=null){queue.offer(ls.right);} //右分支加入队列
}
}
}如上面的算法，我们先将根节点压入队列，之后通过一层while（和之后的左右分支入队）来实现二叉树的遍历。之后通过遍历floor来记录当前计算的层数，并通过size表示这个层有多少元素。
我们通过size为基准，再次使用while，此时遍历的为当前floor的所有元素，并将左右分支入队。
这个方法主要使用了记录size，通过每次遍历完一层，将元素全部出队，并在下一层循环开始前记录此时的size，来区分每一层有几个元素，以此实现方法。
