LeetCode - Easy - 107. Binary Tree Level Order Traversal II

柔情只为你懂 2022-12-28 06:22 155阅读 0赞

## Topic ##

*  Tree
 *  Depth-first Search
 *  Breadth-first Search

## Description ##

[https://leetcode.com/problems/binary-tree-level-order-traversal-ii/][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]
    ]

## Analysis ##

方法一：BFS

方法二：DFS

## Submission ##

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.LinkedList;
    import java.util.List;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class BinaryTreeLevelOrderTraversalII { 
    	
    	//方法一：BFS
    	public List<List<Integer>> levelOrderBottom1(TreeNode root) { 
    		List<List<Integer>> result = new LinkedList<>();
    		if (root == null)
    			return result;
    		TreeNode p = root;
    		LinkedList<TreeNode> queue = new LinkedList<>(Arrays.asList(p));
    
    		while (!queue.isEmpty()) { 
    			int size = queue.size();
    			List<Integer> list = new ArrayList<>();
    
    			while (size-- > 0) { 
    				p = queue.poll();
    
    				if (p.left != null) { 
    					queue.offer(p.left);
    				}
    
    				if (p.right != null) { 
    					queue.offer(p.right);
    				}
    
    				list.add(p.val);
    			}
    			result.add(0, list);
    		}
    
    		return result;
    	}
    
    	//方法二：DFS
    	public List<List<Integer>> levelOrderBottom2(TreeNode root) { 
    		List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
    		levelOrderBottom2(wrapList, root, 0);
    		return wrapList;
    	}
    
    	public void levelOrderBottom2(List<List<Integer>> list, TreeNode root, int level) { 
    		if (root == null)
    			return;
    		if (level >= list.size()) { 
    			list.add(0, new LinkedList<Integer>());
    		}
    		levelOrderBottom2(list, root.left, level + 1);
    		levelOrderBottom2(list, root.right, level + 1);
    		list.get(list.size() - level - 1).add(root.val);
    	}
    }

## Test ##

import static org.junit.Assert.*;
    import static org.hamcrest.CoreMatchers.*;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    import org.junit.Test;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class BinaryTreeLevelOrderTraversalIITest { 
    
    	@Test
    	public void test() { 
    		BinaryTreeLevelOrderTraversalII obj = new BinaryTreeLevelOrderTraversalII();
    		List<List<Integer>> expected = new ArrayList<>(
    				Arrays.asList(Arrays.asList(15, 7), Arrays.asList(9, 20), Arrays.asList(3)));
    
    		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);
    
    		assertThat(obj.levelOrderBottom1(root), is(expected));
    		assertThat(obj.levelOrderBottom2(root), is(expected));
    	}
    }

[https_leetcode.com_problems_binary-tree-level-order-traversal-ii]: https://leetcode.com/problems/binary-tree-level-order-traversal-ii/