首页 > 代码库 > 【LeetCode-面试算法经典-Java实现】【107-Binary Tree Level Order Traversal II(二叉树层序遍历II)】

【LeetCode-面试算法经典-Java实现】【107-Binary Tree Level Order Traversal II(二叉树层序遍历II)】

【107-Binary Tree Level Order Traversal II(二叉树层序遍历II)】


【LeetCode-面试算法经典-Java实现】【全部题目文件夹索引】

原题

  Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).
  For example:
  Given binary tree {3,9,20,#,#,15,7},

    3
   /   9  20
    /     15   7

  return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

题目大意

  给定一棵二叉树自底向下进行层序遍历。

解题思路

  对树进行层序遍历,每层的结果放在结果链表的头部。


代码实现

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

算法实现类

import java.util.*;

public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {

        List<List<Integer>> list = new LinkedList<>();
        if (root == null) {
            return list;
        }

        Deque<TreeNode> cur = new LinkedList<>();
        Deque<TreeNode> nxt = new LinkedList<>();
        Deque<TreeNode> exc = new LinkedList<>();

        TreeNode tmp;

        cur.add(root);
        while (!cur.isEmpty()) {
            List<Integer> layout = new ArrayList<>();

            while (!cur.isEmpty()) {
                tmp = cur.remove();

                if (tmp.left != null) {
                    nxt.add(tmp.left);
                }

                if (tmp.right != null) {
                    nxt.add(tmp.right);
                }

                layout.add(tmp.val);
            }

            exc = cur;
            cur = nxt;
            nxt = exc;

            list.add(0, layout);
        }

        return list;
    }
}

评測结果

  点击图片,鼠标不释放,拖动一段位置。释放后在新的窗体中查看完整图片。

技术分享

特别说明

欢迎转载,转载请注明出处【http://blog.csdn.net/derrantcm/article/details/47392965】

<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

【LeetCode-面试算法经典-Java实现】【107-Binary Tree Level Order Traversal II(二叉树层序遍历II)】