623. Add One Row to Tree #

Problem #

Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1.

The adding rule is: given a positive integer depth d, for each NOT null tree nodes N in depth d-1, create two tree nodes with value v as N's left subtree root and right subtree root. And N's original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root’s left subtree.

Example 1:

Input: 
A binary tree as following:
       4
     /   \
    2     6
   / \   / 
  3   1 5   

v = 1d = 2Output: 
       4
      / \
     1   1
    /     \
   2       6
  / \     / 
 3   1   5   

Example 2:

Input: 
A binary tree as following:
      4
     /   
    2    
   / \   
  3   1    

v = 1d = 3Output: 
      4
     /   
    2
   / \    
  1   1
 /     \  
3       1

Note:

1. The given d is in range [1, maximum depth of the given tree + 1].
2. The given binary tree has at least one tree node.

Summary #

Given a binary tree, with the root node at level 1 and depth 1. Add a row of nodes with value v at its d-th level. Adding rule: given a depth value d (positive integer), for each non-null node N at depth d-1, create two left and right subtree nodes with value v for N. Connect N’s original left subtree as the left subtree of the new node v; connect N’s original right subtree as the right subtree of the new node v. If the value of d is 1, depth d - 1 does not exist, so create a new root node v, and the entire original tree will be the left subtree of v.

Solution Approach #

• Although this problem is Medium, it is actually very simple. To add a row to a binary tree, use DFS or BFS, record the level during traversal, and when reaching the target row, add the nodes. However, pay attention to 2 special cases. Special case one: d==1, where the row to be added is the root node. Special case two: d>height(root), meaning the row to be added is higher than the tree; in this case, only add one layer to the bottom leaf nodes. Time complexity is O(n), and space complexity is O(n).

Code #

package leetcode

import (
	"github.com/halfrost/leetcode-go/structures"
)

// TreeNode define
type TreeNode = structures.TreeNode

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func addOneRow(root *TreeNode, v int, d int) *TreeNode {
	if d == 1 {
		tmp := &TreeNode{Val: v, Left: root, Right: nil}
		return tmp
	}
	level := 1
	addTreeRow(root, v, d, &level)
	return root
}

func addTreeRow(root *TreeNode, v, d int, currLevel *int) {
	if *currLevel == d-1 {
		root.Left = &TreeNode{Val: v, Left: root.Left, Right: nil}
		root.Right = &TreeNode{Val: v, Left: nil, Right: root.Right}
		return
	}
	*currLevel++
	if root.Left != nil {
		addTreeRow(root.Left, v, d, currLevel)
	}
	if root.Right != nil {
		addTreeRow(root.Right, v, d, currLevel)
	}
	*currLevel--
}