二叉樹的層平均值

題目.png

//節(jié)點的數(shù)據結構
  Definition for a binary tree node.
  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
   TreeNode(int x) { val = x; }
}

對于此題而言，我們使用廣度優(yōu)先算法來遍歷二叉樹。

1、深度優(yōu)先算法是根據二叉樹的路徑進行遍歷
2、廣度優(yōu)先算法是根據二叉樹的層級進行遍歷

如何針對二叉樹的層級進行遍歷呢？

• 使用Queue隊列，每遍歷一層節(jié)點，則將該層節(jié)點出隊，并將該層節(jié)點的子節(jié)點進隊。

隊列是一種特殊的線性表，它只允許在表的前端進行刪除操作，而在表的后端進行插入操作。

• 因為隊列的特殊性，當前層節(jié)點永遠在隊首，子節(jié)點永遠在隊尾。所以我們通過循環(huán)當前層的size次，就完成遍歷當前層所有節(jié)點。

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        //結果集
        List<Double> resultList = new ArrayList<Double>();
        //隊列，用來計算平均值
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //判斷非空
        if(root == null) return resultList;
        //根節(jié)點入隊
        queue.offer(root);
        //按層級循環(huán)，當隊列為空時，則已經結束最后一層。則結束
        while(!queue.isEmpty()){
            //節(jié)點數(shù)
            double size = queue.size();
            //每層的節(jié)點和
            double sum = 0;
            //按每層節(jié)點數(shù)循環(huán)
            for(int i=0;i<size;i++){
                //出隊
                root = queue.poll();
                //求和
                sum+=root.val;
                //判斷是否存在左右節(jié)點，有則入隊
                if(root.left != null) queue.offer(root.left);
                if(root.right != null) queue.offer(root.right);
            }
            //將每層的節(jié)點均值加入數(shù)組
            resultList.add(sum/size);
        }
        return resultList;
    }
}