​Summary 623 of the force buckle solution - add a row to the binary tree

Directory link:

Likou Programming Questions-Solution Summary_Share + Record-CSDN Blog

GitHub synchronization brushing project:

https://github.com/September26/java-algorithms

Original link:

Leave

Description:

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

Note that the root node root is at depth 1.

The addition rules are as follows:

Given an integer depth, for each non-empty tree node cur of depth - 1, create two tree nodes of value val as the left and right sub-roots of cur .
cur The original left subtree should be the left subtree of the root of the new left subtree.
cur The original right subtree should be the right subtree of the root of the new right subtree.
If depth == 1 means that depth - 1 has no depth at all, then create a tree node with value val as the new root of the entire original tree, which is the left subtree of the new root.

Example 1:

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:

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

Tips:

The number of nodes is in the range [1, 104]
The depth of the tree is in the range [1, 104]
-100 <= Node.val <= 100
-105 <= val <=105
1 <= depth <= the depth of tree + 1

Source: LeetCode
Link: https://leetcode.cn/problems/add-one-row-to-tree
The copyright belongs to LeetCode.com.For commercial reprints, please contact the official authorization, and for non-commercial reprints, please indicate the source.

Solution ideas:

* Problem-solving ideas:* Recursive judgment, divided into three scenarios:* When depath level, recursive judgment is required.It should be noted here that if the root itself has only three levels, but when depth=4, nodes should also be added.So handle the scenario where root.left == null and depth == level + 1* When depth == level, you need to judge ifLeft. If it is true, parentNode.left = newNode; and newNode.left = root;, and the operation is similar when false.

Code:

public class Solution623 {public TreeNode addOneRow(TreeNode root, int val, int depth) {return addOneRowByLevel(root, val, depth, 1, true, null);}private TreeNode addOneRowByLevel(TreeNode root, int val, int depth, int level, boolean isLeft, TreeNode parentNode) {if (depth < level) {return root;}if (depth > level) {if (root.left != null) {addOneRowByLevel(root.left, val, depth, level + 1, true, root);} else if (depth == level + 1) {root.left = new TreeNode(val);}if (root.right != null) {addOneRowByLevel(root.right, val, depth, level + 1, false, root);} else if (depth == level + 1) {root.right = new TreeNode(val);}return root;}TreeNode newNode = new TreeNode(val);if (isLeft) {newNode.left = root;if (parentNode != null) {parentNode.left = newNode;}} else {newNode.right = root;parentNode.right = newNode;}return newNode;}}