LeetCode - Medium - 655. Print Binary Tree

喜欢ヅ旅行 2022-10-16 08:53 2阅读 0赞

## Topic ##

*  Tree

## Description ##

[https://leetcode.com/problems/print-binary-tree/][https_leetcode.com_problems_print-binary-tree]

Given the `root` of a binary tree, construct a **0-indexed** `m x n` string matrix `res` that represents a **formatted layout** of the tree. The formatted layout matrix should be constructed using the following rules:

*  The **height** of the tree is `height` and the number of rows `m` should be equal to `height + 1`.
 *  The number of columns `n` should be equal to  2 h e i g h t + 1 − 1 2^\{height+1\} - 1 2height\+1−1.
 *  Place the **root node** in the **middle** of the **top row** (more formally, at location `res[0][(n-1)/2]`).
 *  For each node that has been placed in the matrix at position `res[r][c]`, place its left child at  r e s \[ r + 1 \] \[ c − 2 h e i g h t − r − 1 \] res\[r+1\]\[c-2^\{height-r-1\}\] res\[r\+1\]\[c−2height−r−1\] and its right child at  r e s \[ r + 1 \] \[ c + 2 h e i g h t − r − 1 \] res\[r+1\]\[c+2^\{height-r-1\}\] res\[r\+1\]\[c\+2height−r−1\].
 *  Continue this process until all the nodes in the tree have been placed.
 *  Any empty cells should contain the empty string `""`.

Return the constructed matrix `res`.

**Example 1:**

![b307b604c25d6c6e697d3a2364379a5f.png][]

Input: root = [1,2]
    Output: 
    [["","1",""],
     ["2","",""]]

**Example 2:**

![95f1789b8f91992e9eeb82535940d46c.png][]

Input: root = [1,2,3,null,4]
    Output: 
    [["","","","1","","",""],
     ["","2","","","","3",""],
     ["","","4","","","",""]]

**Constraints:**

*  The number of nodes in the tree is in the range  \[ 1 , 2 10 \] \[1, 2^\{10\}\] \[1,210\].
 *  \-99 <= Node.val <= 99
 *  The depth of the tree will be in the range \[1, 10\].

## Analysis ##

方法一：BFS，我写的。

方法二：别人写的，DFS（或二叉树的前序遍历）

## Submission ##

import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class PrintBinaryTree { 
    	
    	//方法一：BFS，我写的
        public List<List<String>> printTree(TreeNode root) { 
            
        	int height = getHeight(root);
        	int m = height + 1, n = (int)Math.pow(2, m) - 1;
        	
        	List<String> emptyRow = new ArrayList<>(n);
        	for(int i = 0; i < n; i++)
        		emptyRow.add("");
        	
        	List<List<String>> result = new ArrayList<>();
        	
        	LinkedList<Object> queue = new LinkedList<>();
        	queue.offer(root);
        	queue.offer(new int[] { 0, (n - 1) / 2});
        	
        	while(!queue.isEmpty()) { 
        		
        		List<String> newRow = new ArrayList<>(emptyRow);
        		for(int size = queue.size(); size > 0; size -= 2) { 
        			
        			TreeNode node = (TreeNode)queue.poll();
        			int[] index = (int[])queue.poll();
        			int r = index[0], c = index[1];
        			
        			newRow.set(c, String.valueOf(node.val));
        			
        			if(node.left != null) { 
        				queue.offer(node.left);
        				queue.offer(new int[] { r + 1, c - (int)Math.pow(2, height - r - 1)});
        			}
        				
        			if(node.right != null) { 
        				queue.offer(node.right);
        				queue.offer(new int[] { r + 1, c + (int)Math.pow(2, height - r - 1)});
        			}
        		}
        		result.add(newRow);
        	}
        	
        	return result;
        }
        
        
        public int getHeight(TreeNode root) { 
        	if(root == null)
        		return 0;
        	
        	int temp = 0;
        	if(root.left != null || root.right != null)
        		temp = 1;
        	
        	return temp + Math.max(getHeight(root.left), getHeight(root.right));
        }
        
        
        //方法二：别人写的，DFS（或二叉树的前序遍历）
        public List<List<String>> printTree2(TreeNode root) { 
            List<List<String>> res = new LinkedList<>();
            int height = root == null ? 1 : getHeight2(root);
            int rows = height, columns = (int) (Math.pow(2, height) - 1);
            List<String> row = new ArrayList<>();
            for(int i = 0; i < columns; i++)  
            	row.add("");
            
            for(int i = 0; i < rows; i++)  
            	res.add(new ArrayList<>(row));
            populateRes(root, res, 0, rows, 0, columns - 1);
            return res;
        }
    
        public void populateRes(TreeNode root, List<List<String>> res, int nRow, int totalRows, int left, int right) { 
            if (nRow == totalRows || root == null) return;
            int mid = left + (right - left) / 2;
            res.get(nRow).set(mid, Integer.toString(root.val));
            populateRes(root.left, res, nRow + 1, totalRows, left, mid - 1);
            populateRes(root.right, res, nRow + 1, totalRows, mid + 1, right);
        }
    
        public int getHeight2(TreeNode root) { 
             if (root == null) return 0;
             return 1 + Math.max(getHeight2(root.left), getHeight2(root.right));
        }
        
    }

## Test ##

import static org.junit.Assert.*;
    import static org.hamcrest.collection.IsIterableContainingInOrder.*;
    
    import java.util.Arrays;
    import java.util.List;
    
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class PrintBinaryTreeTest { 
    
    	@Test
    	public void testGetHeight() { 
    		PrintBinaryTree obj = new PrintBinaryTree();
    
    		assertEquals(1, obj.getHeight(BinaryTree.integers2BinaryTree(1, 2)));
    		assertEquals(2, obj.getHeight(BinaryTree.integers2BinaryTree(1, 2, 3, null, 4)));
    	}
    	
    	@Test
    	@SuppressWarnings({  "rawtypes" })
    	public void test() { 
    		PrintBinaryTree obj = new PrintBinaryTree();
    		
    		TreeNode root1 = BinaryTree.integers2BinaryTree(1, 2);
    		TreeNode root2 = BinaryTree.integers2BinaryTree(1, 2, 3, null, 4);
    		
    		List[] expected1 = { Arrays.asList("","1",""), //
    							Arrays.asList("2","","")};
    		
    		List[] expected2 = { Arrays.asList("","","","1","","",""), // 
    							Arrays.asList("","2","","","","3",""), //
    							Arrays.asList("","","4","","","","")};
    		
    		assertThat(obj.printTree(root1), contains(expected1));
    		assertThat(obj.printTree(root2), contains(expected2));
    		
    		assertThat(obj.printTree2(root1), contains(expected1));
    		assertThat(obj.printTree2(root2), contains(expected2));
    		
    	}
    }

[https_leetcode.com_problems_print-binary-tree]: https://leetcode.com/problems/print-binary-tree/
[b307b604c25d6c6e697d3a2364379a5f.png]: /images/20221014/5acf16c218a04e4382391323285b5393.png
[95f1789b8f91992e9eeb82535940d46c.png]: /images/20221014/6a3a86764fa7425ba559fb6257d21639.png