【Leetcode】107. 二叉樹的層次遍歷 II
題目
給定一個二叉樹,返回其節點值自底向上的層次遍歷。 (即按從葉子節點所在層到根節點所在的層,逐層從左向右遍歷)
例如:
給定二叉樹 [3,9,20,null,null,15,7],
3 / \ 920 /\ 157
返回其自底向上的層次遍歷為:
[ [15,7], [9,20], [3] ]
題解
利用層次遍歷,層次遍歷的時候進入下一層的時候記錄一下當前佇列中有幾個元素。
class Solution { public List<List<Integer>> levelOrderBottom(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> levelVal = new LinkedList<>(); while (size > 0) { TreeNode current = queue.poll(); if (current.left != null) { queue.add(current.left); } if (current.right != null) { queue.add(current.right); } levelVal.add(current.val); size--; } res.add(0, levelVal); } return res; } }
用遞迴去做。
用遞迴去做的關鍵在於需要把層數也帶上。
class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } helper(root, res, 0); return res; } public void helper(TreeNode root, List<List<Integer>> res, int depth) { if (root == null) { return; } if (depth == res.size()) { res.add(0, new LinkedList<>()); } List<Integer> current = res.get(res.size() - depth - 1); helper(root.left, res, depth + 1); helper(root.right, res, depth + 1); current.add(root.val); } }
熱門閱讀
- 技術文章彙總
- 【Leetcode】103. 二叉樹的鋸齒形層次遍歷
- 【Leetcode】102. 二叉樹的層次遍歷
- 【Leetcode】101. 對稱二叉樹
- 【Leetcode】100. 相同的樹
- 【Leetcode】98. 驗證二叉搜尋樹
手撕程式碼QQ群:805423079, 群密碼:1024