Binary Tree Level Order Traversal II

Question

  1. Given a binary tree, return the bottom-up level order traversal of its nodes' values.
  2. (ie, from left to right, level by level from leaf to root).
  4. Example
  5. Given binary tree {3,9,20,#,#,15,7},
  7.     3
  8.    / \
  9.   9  20
  10.     /  \
  11.    15   7
  14. return its bottom-up level order traversal as:
  15. [
  16.   [15,7],
  17.   [9,20],
  18.   [3]
  19. ]

題解

這題在普通的 BFS 基礎上增加了逆序輸出，簡單的實現可以使用 Stack 或者最後對結果逆序。

Java - Stack

  1. /**
  2.  * Definition of TreeNode:
  3.  * public class TreeNode {
  4.  *     public int val;
  5.  *     public TreeNode left, right;
  6.  *     public TreeNode(int val) {
  7.  *         this.val = val;
  8.  *         this.left = this.right = null;
  9.  *     }
  10.  * }
  11.  */
  14. public class Solution {
  15.     /**
  16.      * @param root: The root of binary tree.
  17.      * @return: buttom-up level order a list of lists of integer
  18.      */
  19.     public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
  20.         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  21.         if (root == null) return result;
  23.         Stack<ArrayList<Integer>> s = new Stack<ArrayList<Integer>>();
  24.         Queue<TreeNode> q = new LinkedList<TreeNode>();
  25.         q.offer(root);
  26.         while (!q.isEmpty()) {
  27.             int qLen = q.size();
  28.             ArrayList<Integer> aList = new ArrayList<Integer>();
  29.             for (int i = 0; i < qLen; i++) {
  30.                 TreeNode node = q.poll();
  31.                 aList.add(node.val);
  32.                 if (node.left != null) q.offer(node.left);
  33.                 if (node.right != null) q.offer(node.right);
  34.             }
  35.             s.push(aList);
  36.         }
  38.         while (!s.empty()) {
  39.             result.add(s.pop());
  40.         }
  41.         return result;
  42.     }
  43. }

Java - Reverse

  1. /**
  2.  * Definition of TreeNode:
  3.  * public class TreeNode {
  4.  *     public int val;
  5.  *     public TreeNode left, right;
  6.  *     public TreeNode(int val) {
  7.  *         this.val = val;
  8.  *         this.left = this.right = null;
  9.  *     }
  10.  * }
  11.  */
  14. public class Solution {
  15.     /**
  16.      * @param root: The root of binary tree.
  17.      * @return: buttom-up level order a list of lists of integer
  18.      */
  19.     public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
  20.         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  21.         if (root == null) return result;
  23.         Queue<TreeNode> q = new LinkedList<TreeNode>();
  24.         q.offer(root);
  25.         while (!q.isEmpty()) {
  26.             int qLen = q.size();
  27.             ArrayList<Integer> aList = new ArrayList<Integer>();
  28.             for (int i = 0; i < qLen; i++) {
  29.                 TreeNode node = q.poll();
  30.                 aList.add(node.val);
  31.                 if (node.left != null) q.offer(node.left);
  32.                 if (node.right != null) q.offer(node.right);
  33.             }
  34.             result.add(aList);
  35.         }
  37.         Collections.reverse(result);
  38.         return result;
  39.     }
  40. }

源碼分析

Java 中 Queue 是接口，通常可用 LinkedList 實例化。

複雜度分析

時間複雜度爲 O(n), 使用了 Queue 或者 Stack 作爲輔助空間，空間複雜度爲 O(n).