LeetCode-107-二叉树的层序遍历 II

二叉树的层序遍历 II

题目描述：给定一个二叉树，返回其节点值自底向上的层序遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例说明请见LeetCode官网。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：层序遍历

首先，如果根节点为空，直接返回空的结果集。

如果根节点不为空，通过队列来遍历每一层的节点，具体处理过程如下：
首先将根节点放入队列；

遍历队列中当前的节点数，即为当前层的结果，然后再将当前层节点的左右非空子节点放入到队列中；

然后继续遍历队列中下一层的节点，直到队列为空位置。

这样得到的结果是从上往下层序遍历的结果，最后调用Collections.reverse(result);这个方法，将得到的结果集逆序排列，即可得到自底向上的层序遍历。

import com.kaesar.leetcode.TreeNode;

import java.util.*;

public class LeetCode_107 {

    /**

     * 层序遍历

     *

     * @param root

     * @return

     */

    public static List<List<Integer>> levelOrderBottom(TreeNode root) {

        // 初始化结果集

        List<List<Integer>> result = new ArrayList<>();

        // 如果根节点为空，直接返回result

        if (root == null) {

            return result;

        }

        // 用一个队列存每一层的节点

        Queue<TreeNode> nodes = new LinkedList<>();

        nodes.add(root);

        // 遍历每一层的节点，将节点的值放入list中

        while (!nodes.isEmpty()) {

            int count = nodes.size();

            List<Integer> curLevel = new ArrayList<>();

            while (count > 0) {

                TreeNode cur = nodes.poll();

                curLevel.add(cur.val);

                if (cur.left != null) {

                    nodes.add(cur.left);

                }

                if (cur.right != null) {

                    nodes.add(cur.right);

                }

                count--;

            }

            result.add(curLevel);

        }

        // 最后将得到的结果集逆序，得到从最下层 -> 最上层的遍历结果

        Collections.reverse(result);

        return result;

    }

    public static void main(String[] args) {

        // 测试用例

        TreeNode root = new TreeNode(3);

        root.left = new TreeNode(9);

        root.right = new TreeNode(20);

        root.right.left = new TreeNode(15);

        root.right.right = new TreeNode(7);

        for (List<Integer> integers : levelOrderBottom(root)) {

            for (Integer integer : integers) {

                System.out.print(integer + " ");

            }

            System.out.println();

        }

    }

}

【每日寄语】 多少事，从来急，天地转，光阴迫，一万年太久，只争朝夕。

巴特西

LeetCode-107-二叉树的层序遍历 II

二叉树的层序遍历 II

解法一：层序遍历

最新文章

热门文章