二叉树同层处理

个人整理,非最优解


二叉树算法中,如果我们需要如:获取每一层二叉树的元素总和时,这样对二叉树每一层进行分开计算,可以使用队列加两层while循环:

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,来区分每一层有几个元素,以此实现方法。