分析

难度 易

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

来源

https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

题目

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

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

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

解答

 1 package LeetCode;
 2 
 3 import java.util.*;
 4 import java.util.logging.Level;
 5 
 6 public class L107_BinaryTreeLevelOrderTraversalII {
 7     /**
 8      * 采用递归的方式创建一颗二叉树
 9      * 传入的是二叉树的数组表示法
10      * 构造后是二叉树的二叉链表表示法
11      */
12     public TreeNode makeBinaryTreeByArray(Integer[] array,int index){
13         if(index<array.length&&array[index]!=null){
14             int value=array[index];
15             TreeNode t=new TreeNode(value);
16             array[index]=0;
17             t.left=makeBinaryTreeByArray(array,index*2+1);
18             t.right=makeBinaryTreeByArray(array,index*2+2);
19             return t;
20         }else
21             return null;
22     }
23 
24     public List<List<Integer>> levelOrderBottom(TreeNode root) {
25         List<Integer> levelList=new ArrayList<Integer>();
26         Stack<List<Integer>> levellistStack=new Stack<List<Integer>>();
27         List<List<Integer>> result=new ArrayList<List<Integer>>();
28         if(root==null){
29             return result;
30         }
31         Queue<TreeNode> queue=new LinkedList<TreeNode>();
32         queue.offer(root);
33         int curCount=1;//记录当前层节点数
34         int nextCount=0;//记录下一层节点数
35         int outCount=0;//记录出队列节点数
36         while(!queue.isEmpty()){
37             TreeNode node=queue.poll();
38             levelList.add(node.val);
39             outCount++;
40             if(node.left!=null){
41                 queue.offer(node.left);
42                 //levelList.add(node.left.val);//视角从子节点加入转换为当前节点输出,
43                 nextCount++;
44             }
45             if(node.right!=null){
46                 queue.offer(node.right);
47                 //levelList.add(node.right.val);
48                 nextCount++;
49             }
50             if(outCount==curCount)//当前层全部出队列
51             {
52                 if(!levelList.isEmpty())
53                     levellistStack.push(levelList);
54                 levelList=new ArrayList<Integer>();
55                 curCount=nextCount;
56                 nextCount=0;
57                 outCount=0;
58             }
59         }
60         while(!levellistStack.isEmpty()){
61             result.add(levellistStack.pop());
62         }
63         return result;
64     }
65 
66 
67        public static void main(String[] args){
68         L107_BinaryTreeLevelOrderTraversalII l107=new L107_BinaryTreeLevelOrderTraversalII();
69         Integer[] values={1,2,3,4,5,6,7};
70         TreeNode root=l107.makeBinaryTreeByArray(values,0);
71         List<List<Integer>> res=l107.levelOrderBottom(root);
72         System.out.println(res.toString());
73     }
74 }

 

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄