【Leetcode】102. 二叉樹的層次遍歷
題目
給定一個二叉樹,返回其按層次遍歷的節點值。 (即逐層地,從左到右訪問所有節點)。
例如:
給定二叉樹: [3,9,20,null,null,15,7],
3 / \ 920 /\ 157
返回其層次遍歷結果:
[ [3], [9,20], [15,7] ]
題解
我們資料結構的書上教的層序遍歷,就是利用一個佇列,不斷的把左子樹和右子樹入隊。但是這個題目還要要求按照層輸出。所以關鍵的問題是:如何確定是在同一層的 。
我們很自然的想到:
如果在入隊之前,把上一層所有的節點出隊,那麼出隊的這些節點就是上一層的列表。
由於佇列是先進先出的資料結構,所以這個列表是從左到右的。
/** * Definition for a binary tree node. * public class TreeNode { *int val; *TreeNode left; *TreeNode right; *TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> currentRes = new LinkedList<>(); // 當前佇列的大小就是上一層的節點個數, 依次出隊 while (size > 0) { TreeNode current = queue.poll(); if (current == null) { continue; } currentRes.add(current.val); // 左子樹和右子樹入隊. if (current.left != null) { queue.add(current.left); } if (current.right != null) { queue.add(current.right); } size--; } res.add(currentRes); } return res; } }
這道題可不可以用非遞迴來解呢?
遞迴的子問題:遍歷當前節點, 對於當前層, 遍歷左子樹的下一層層,遍歷右子樹的下一層
遞迴結束條件: 當前層,當前子樹節點是null
/** * Definition for a binary tree node. * public class TreeNode { *int val; *TreeNode left; *TreeNode right; *TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } levelOrderHelper(res, root, 0); return res; } /** * @param depth 二叉樹的深度 */ private void levelOrderHelper(List<List<Integer>> res, TreeNode root, int depth) { if (root == null) { return; } if (res.size() <= depth) { // 當前層的第一個節點,需要new 一個list來存當前層. res.add(new LinkedList<>()); } // depth 層,把當前節點加入 res.get(depth).add(root.val); // 遞迴的遍歷下一層. levelOrderHelper(res, root.left, depth + 1); levelOrderHelper(res, root.right, depth + 1); } }