建設(shè)工程施工包括哪些工程深圳純手工seo
題目
從上到下打印出二叉樹的每個節(jié)點，同一層的節(jié)點按照從左到右的順序打印。
例如:
給定二叉樹:?[3,9,20,null,null,15,7],
??? 3
?? / \
? 9? 20
??? /? \
?? 15?? 7
返回：
[3,9,20,15,7]
提示：
節(jié)點總數(shù) <= 1000
解題思路
1.題目要求我們從上到下打印出二叉樹的每個節(jié)點，同一層的節(jié)點按照從左到右的順序打印。也就是按照二叉樹的層序遍歷打印二叉樹。
2.我們只需要一個隊列即可實現(xiàn)，首先我們判斷樹是否為空，若為空則返回一個沒有元素的數(shù)組。然后我們建立一個隊列來執(zhí)行打印操作，再建立一個可變數(shù)組來存放遍歷后的元素，因為我們不確定所給樹的元素的個數(shù)，所以需要一個可變數(shù)組。
3.下面我們開始遍歷，首先我們將根節(jié)點入隊。然后進(jìn)入一個while（）循環(huán)，若隊列不為空則將讓隊列進(jìn)行出隊操作，然后將剛出隊的元素保存在可變數(shù)組中，再判斷此元素是否有左右孩子，若存在左右孩子就將左右孩子入隊。之后再次判斷隊列是否為空。循環(huán)往復(fù)，直到隊列為空，就代表整棵樹已經(jīng)遍歷完了。
4.最后我們需要將可變數(shù)組中的元素存入一個數(shù)組并且返回即可。
舉個例子：
先讓三入隊
?queue 不為空，讓 3 出隊，并且讓 3 的左右孩子入隊。
?queue 不為空讓 9 出隊，因為 9 沒有左右孩子，所以不進(jìn)行入隊操作
?queue 不為空?讓 20 出隊，并且讓 20 的左右孩子入隊。
?queue 不為空讓 15 出棧，15 沒有左右孩子? ，所以不進(jìn)行入隊操作
??queue 不為空讓 7?出棧，7?沒有左右孩子? ，所以不進(jìn)行入隊操作
?
?queue 為空，打印結(jié)束。
代碼實現(xiàn)
class Solution {public int[] levelOrder(TreeNode root) {if(root == null){return new int[0];}Queue<TreeNode> queue = new LinkedList<>();List<Integer> res = new ArrayList<>();queue.add(root);while(!queue.isEmpty()){TreeNode cur = queue.poll();res.add(cur.val);if(cur.left != null) queue.add(cur.left);if(cur.right != null) queue.add(cur.right);}int[] num = new int[res.size()];for(int i = 0; i < res.size(); i++){num[i] = res.get(i);}return num;}
}測試結(jié)果
?