leetcode binary-tree-level-order-traversal-ii(Java)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了leetcode binary-tree-level-order-traversal-ii(Java)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2119字，纯文字阅读大概需要4分钟。

内容图文

leetcode题目

binary-tree-level-order-traversal-ii -- newcoder 42
二叉树的层次遍历 II -- leetcode 107

题目描述

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],
]

思路

1、(BFS思想)利用队列进行层次遍历
2、反转层次遍历结果 

代码

package com.my.test.leetcode.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 题目：
 * binary-tree-level-order-traversal-ii -- newcoder 42
 * 二叉树的层次遍历 II -- leetcode 107
 * 
 * 题目描述：
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 BinaryTreeLevelOrderTraversalII
{
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    
    /**
     * 思路：
     * 1、利用队列进行层次遍历 
     */
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        
        if (root == null) {
            return ret;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        // 当前处理的节点
        TreeNode curNode;
        
        while (!queue.isEmpty()) {
            // 遍历本层元素, 并把结果加入返回列表中
            int size = queue.size();
            ArrayList<Integer> curList = new ArrayList<>();
            for (int i=0; i<size; i++) {
                curNode = queue.poll();
                // 当前值入列表
                curList.add(curNode.val);
                
                // 下层元素入队列
                if (curNode.left != null) {
                    queue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    queue.offer(curNode.right);
                }
            }
            
            // 当前层元素加入待返回列表
            ret.add(curList);
        }
        
        Collections.reverse(ret);
        
        return ret;
    }
    
    public static void main(String[] args)
    {
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        
        root.left = node1;
        root.right = node2;
        
        System.out.println(new BinaryTreeLevelOrderTraversalII().levelOrderBottom(root));
    }

}

内容总结

以上是互联网集市为您收集整理的leetcode binary-tree-level-order-traversal-ii(Java)全部内容，希望文章能够帮你解决leetcode binary-tree-level-order-traversal-ii(Java)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端