623. Add a row to the binary tree

Date: 2022/8/5

Title description: Given a binary tree root root and two integers val and depth , add a node row 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:

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

Thinking:

dfs, continue to traverse if the corresponding depth is not traversed, and connect when traversed

Code + Analysis:

class Solution {public:TreeNode* addOneRow(TreeNode* root, int val, int depth) {if(depth == 1){TreeNode* node = new TreeNode(val,root,nullptr);return node;}dfs(root,depth,1,val);return root;}void dfs(TreeNode* root,int depth,int floor,int val){if(root == nullptr) return;if(floor+1 == depth){TreeNode* leftNode = new TreeNode(val,root->left,nullptr);TreeNode* rightNode = new TreeNode(val,nullptr,root->right);root->left = leftNode;root->right = rightNode;return;}//else if(floor < depth-1)dfs(root->left,depth,floor+1,val);dfs(root->right,depth,floor+1,val);}};