leetcode_BinaryTreeLevelOrderTraversal

leetcode_BinaryTreeLevelOrderTraversal

題目描述

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:

Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

解題思路

題目要就即實現二叉樹的層次遍歷，類似的還有前序(DLR)、中序(LDR)、後序(LRD)遍歷，後三種使用遞歸很容易實現，同樣也可以利用棧來輔助以實現非遞歸算法，有些實現起來可能比較麻煩。這裡我們要求層次遍歷，利用輔助隊列來實現層次遍歷，由於這裡輸出的要求是按層次的，我們記錄節點的層次信息，同一層次的遍歷的時候(從隊列裡彈出的時候)放到一個集合裡，遍歷完一個層次之後將該層子節點集合加入到 List

詳細代碼

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {

    //Binary Tree Level Order Traversal

    //自定義帶有層次信息的節點信息結構
    class TreeNodeWithDepth
    {
        TreeNode treeNode;
        int depth;

        public TreeNodeWithDepth(TreeNode treeNode, int depth)
        {
            this.treeNode = treeNode;
            this.depth = depth;
        }
    }

    public List> levelOrder(TreeNode root) {
        int depth = 1;
        int lastLevel = 1; //while中用來標示上一次節點的level
        List> resultsList = new ArrayList>();  //注意初始化 List是接口類
        Queue queue = new LinkedList<>();
        TreeNodeWithDepth pNode = null;
        if(root != null)
        {
            pNode = new TreeNodeWithDepth(root, 1);
            queue.offer(pNode);
        }
        List listPerLevel = new ArrayList<>();//每層的list 
        while(!queue.isEmpty())
        {
            pNode = queue.poll();//程序加入時已經判斷不為空節點

            if(pNode.depth > lastLevel)
            {
                //說明是新的一層
                if(listPerLevel.size()!=0)
                {
                    //把上一層的列表加入result中
                    resultsList.add(listPerLevel);
                }
                listPerLevel = new ArrayList<>(); //重新另起一個listPerLevel
                listPerLevel.add(pNode.treeNode.val);//在新列表中加入當前節點
                lastLevel = pNode.depth;//更新lastLevel
            }
            else 
            {
                listPerLevel.add(pNode.treeNode.val);
            }
            //確定子節點深度
            depth = pNode.depth+1;

            //子節點入隊列
            if(pNode.treeNode.left != null)
            {
                queue.offer(new TreeNodeWithDepth(pNode.treeNode.left, depth));
            }
            if(pNode.treeNode.right != null)
            {
                queue.offer(new TreeNodeWithDepth(pNode.treeNode.right, depth));
            }

        }

        //while循環中最後一次的listPerLevel也要加入
        if(listPerLevel.size()>0)
        {
            resultsList.add(listPerLevel);
        }
        return resultsList;
    }
}