给定一个二叉树,返回其节点值自底向上的层序遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

例如:
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其自底向上的层序遍历为:

[
  [15,7],
  [9,20],
  [3]
]
Related Topics
  • 广度优先搜索
  • \n
  • 👍 431
  • 👎 0
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    //给定一个二叉树,返回其节点值自底向上的层序遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历) 
    //
    // 例如:
    //给定二叉树 [3,9,20,null,null,15,7],
    //
    //
    // 3
    // / \
    // 9 20
    // / \
    // 15 7
    //
    //
    // 返回其自底向上的层序遍历为:
    //
    //
    //[
    // [15,7],
    // [9,20],
    // [3]
    //]
    //
    // Related Topics 树 广度优先搜索
    // 👍 431 👎 0


    //leetcode submit region begin(Prohibit modification and deletion)
    /**
    * Definition for a binary tree node.
    * public class TreeNode {
    * int val;
    * TreeNode left;
    * TreeNode right;
    * TreeNode() {}
    * TreeNode(int val) { this.val = val; }
    * TreeNode(int val, TreeNode left, TreeNode right) {
    * this.val = val;
    * this.left = left;
    * this.right = right;
    * }
    * }
    */
    class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
    List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();
    if (root == null) {
    return levelOrder;
    }
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    while (!queue.isEmpty()) {
    List<Integer> level = new ArrayList<Integer>();
    int size = queue.size();
    for (int i = 0; i < size; i++) {
    TreeNode node = queue.poll();
    level.add(node.val);
    TreeNode left = node.left, right = node.right;
    if (left != null) {
    queue.offer(left);
    }
    if (right != null) {
    queue.offer(right);
    }
    }
    levelOrder.add(0, level);
    }
    return levelOrder;
    }
    }
    //leetcode submit region end(Prohibit modification and deletion)