107. 二叉树的层序遍历 II

╰+哭是因爲堅強的太久メ 2023-10-05 21:21 57阅读 0赞

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

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

3
       / \
      9  20
        /  \
       15   7

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

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

package Solution107;
    
    import java.util.Collections;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    
    class Solution2 {
    	public List<List<Integer>> levelOrderBottom(TreeNode root) {
    		if (root == null) {
    			return Collections.emptyList();
    		}
    		Queue<TreeNode> queue = new LinkedList<TreeNode>();
    		queue.add(root);
    		int count = 1;
    		LinkedList<List<Integer>> finalList = new LinkedList<List<Integer>>();
    		while (count != 0) {
    			List<Integer> list = new LinkedList<Integer>();
    			Queue<TreeNode> nextQueue = new LinkedList<TreeNode>();
    			while (!queue.isEmpty()) {
    				TreeNode node = queue.poll();
    				list.add(node.val);
    				count--;
    				if (node.left != null) {
    					nextQueue.add(node.left);
    				}
    				if (node.right != null) {
    					nextQueue.add(node.right);
    				}
    			}
    			finalList.addFirst(list);
    
    			count = nextQueue.size();
    			queue = nextQueue;
    		}
    		return finalList;
    	}
    
    	public static void main(String[] args) {
    
    		Solution2 same = new Solution2();
    
    		TreeNode first = new TreeNode(3);
    		first.left = new TreeNode(9);
    		first.right = new TreeNode(20);
    		first.right.left = new TreeNode(15);
    		first.right.right = new TreeNode(7);
    
    		System.out.println(same.levelOrderBottom(first));
    	}
    
    }