LeetCode - Medium - 623. Add One Row to Tree

旧城等待， 2022-10-17 04:08 55阅读 0赞

## Topic ##

*  Tree

## Description ##

[https://leetcode.com/problems/add-one-row-to-tree/][https_leetcode.com_problems_add-one-row-to-tree]

Given the `root` of a binary tree and two integers `val` and K, add a row of nodes with value `val` at the given depth `depth`.

Note that the `root` node is at depth `1`.

The adding rule is:

*  Given the integer `depth`, for each not null tree node `cur` at the depth `depth - 1`, create two tree nodes with value `val` as `cur`'s left subtree root and right subtree root.
 *  `cur`'s original left subtree should be the left subtree of the new left subtree root.
 *  `cur`'s original right subtree should be the right subtree of the new right subtree root.
 *  If `depth == 1` that means there is no depth `depth - 1` at all, then create a tree node with value `val` as the new root of the whole original tree, and the original tree is the new root’s left subtree.

**Example 1:**

![49408b8d9afd439f189525e4df2f085f.png][]

Input: root = [4,2,6,3,1,5], val = 1, depth = 2
    Output: [4,1,1,2,null,null,6,3,1,5]

**Example 2:**

![d98d3cd2d9c86cb3084bdaa7a5385142.png][]

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

**Constraints:**

*  The number of nodes in the tree is in the range  \[ 1 , 1 0 4 \] \[1, 10^4\] \[1,104\].
 *  The depth of the tree is in the range  \[ 1 , 1 0 4 \] \[1, 10^4\] \[1,104\].
 *   − 100 < = N o d e . v a l < = 100 -100 <= Node.val <= 100 −100<=Node.val<=100
 *   − 1 0 5 < = v a l < = 1 0 5 -10^5 <= val <= 10^5 −105<=val<=105
 *   1 < = d e p t h < = t h e   d e p t h   o f   t r e e + 1 1 <= depth <= the\\ depth\\ of\\ tree + 1 1<=depth<=the depth of tree\+1

## Analysis ##

方法一：BFS

方法二：DFS

## Submission ##

import java.util.LinkedList;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class AddOneRowToTree { 
    	
    	//方法一：BFS
        public TreeNode addOneRow(TreeNode root, int val, int depth) { 
        	if(depth == 1) { 
        		return new TreeNode(val, root, null);
        	}
    		LinkedList<TreeNode> queue = new LinkedList<>();
    		queue.offer(root);
    		int level = 1;
    		
    		while(!queue.isEmpty()) { 
    			
    			++level;
    			for(int size = queue.size(); size > 0; size--) { 
        			TreeNode node = queue.poll();
        			
        			if(level == depth) { 
        				node.left = new TreeNode(val, node.left, null);
        				node.right = new TreeNode(val, null, node.right);
        			}else { 
        				if(node.left != null)
        					queue.offer(node.left);
        				
        				if(node.right != null)
        					queue.offer(node.right);
        			}
    			}
    		}
    		
    		return root;
        }
        
        //方法二：DFS
        public TreeNode addOneRow2(TreeNode root, int val, int depth) { 
        	if(depth == 1) { 
        		return new TreeNode(val, root, null);
        	}
    		addOneRow2(root, val, depth, 1);
    		return root;
        }
        
        private void addOneRow2(TreeNode node, int val, int depth, int level) { 
        	if(node == null) return;
        	
        	if(++level == depth) { 
        		node.left = new TreeNode(val, node.left, null);
    			node.right = new TreeNode(val, null, node.right);
    			return;
        	}
        	addOneRow2(node.left, val, depth, level);
        	addOneRow2(node.right, val, depth, level);
        }
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class AddOneRowToTreeTest { 
    
    	@Test
    	public void test() { 
    		AddOneRowToTree obj = new AddOneRowToTree();
    
    		TreeNode root1 = BinaryTree.integers2BinaryTree(4, 2, 6, 3, 1, 5);
    		TreeNode expected1 = BinaryTree.integers2BinaryTree(4, 1, 1, 2, null, null, 6, 3, 1, 5);
    		assertTrue(BinaryTree.equals(obj.addOneRow(root1, 1, 2), expected1));
    		
    		TreeNode root2 = BinaryTree.integers2BinaryTree(4, 2, null, 3, 1);
    		TreeNode expected2 = BinaryTree.integers2BinaryTree(4, 2, null, 1, 1, 3, null, null, 1);
    		assertTrue(BinaryTree.equals(obj.addOneRow(root2, 1, 3), expected2));
    		
    		TreeNode root3 = BinaryTree.integers2BinaryTree(1, 2, 3, 4);
    		TreeNode expected3 = BinaryTree.integers2BinaryTree(1, 2, 3, 4, null, null, null, 5, 5);
    		assertTrue(BinaryTree.equals(obj.addOneRow(root3, 5, 4), expected3));
    	}
    	
    	@Test
    	public void test2() { 
    		AddOneRowToTree obj = new AddOneRowToTree();
    		
    		TreeNode root1 = BinaryTree.integers2BinaryTree(4, 2, 6, 3, 1, 5);
    		TreeNode expected1 = BinaryTree.integers2BinaryTree(4, 1, 1, 2, null, null, 6, 3, 1, 5);
    		assertTrue(BinaryTree.equals(obj.addOneRow2(root1, 1, 2), expected1));
    		
    		TreeNode root2 = BinaryTree.integers2BinaryTree(4, 2, null, 3, 1);
    		TreeNode expected2 = BinaryTree.integers2BinaryTree(4, 2, null, 1, 1, 3, null, null, 1);
    		assertTrue(BinaryTree.equals(obj.addOneRow2(root2, 1, 3), expected2));
    		
    		TreeNode root3 = BinaryTree.integers2BinaryTree(1, 2, 3, 4);
    		TreeNode expected3 = BinaryTree.integers2BinaryTree(1, 2, 3, 4, null, null, null, 5, 5);
    		assertTrue(BinaryTree.equals(obj.addOneRow2(root3, 5, 4), expected3));
    	}
    }

[https_leetcode.com_problems_add-one-row-to-tree]: https://leetcode.com/problems/add-one-row-to-tree/
[49408b8d9afd439f189525e4df2f085f.png]: /images/20221014/3cd1937de99047e19caf1a4fe9f04b67.png
[d98d3cd2d9c86cb3084bdaa7a5385142.png]: /images/20221014/ada268e45cda493984d79b1855c3bdf2.png