题目链接：https://leetcode.cn/problems/add-one-row-to-tree/
思路
方法一、DFS
直接想法
这题的要求：根节点为深度1开始，在depth深度创建一个新的节点，把原来depth深度的节点，父节点的左子节点依旧为新节点的左子节点，右子节点依旧为新节点的右子节点。
这个时候我们可以用DFS从根节点开始遍历节点的左右节点，一直找到depth深度的节点，创建新的节点替换他，然后返回给父节点新的节点，对于depth深度存在问题，这里我们需要分类讨论
1.depth深度为1：需要在根节点创建新的节点，去替代根节点
2.depth深度在(1，n)：这里的n是树的深度，就是在树中间插入节点，用DFS遍历递归到相应节点进行替换
3.depth深度在n：在树的叶子节点出插入新节点，不需要替换，只需要创建新的节点即可
代码示例
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func addOneRow(root *TreeNode, val int, depth int) *TreeNode { var dfs func(root *TreeNode, depth int, flag int) *TreeNode dfs = func(root *TreeNode, depth int, flag int) *TreeNode{ if depth == 1{ var node *TreeNode if flag == 1{ node = &TreeNode{ Val: val, Left: root, Right: nil, } }else{ node = &TreeNode{ Val: val, Left: nil, Right: root, } } return node } if root == nil{ return nil } root.Left = dfs(root.Left, depth - 1, 1) root.Right = dfs(root.Right, depth - 1, 0) return root } return dfs(root, depth, 1) }
复杂度分析
- 时间复杂度：O(2depth - 1)，表示遍历到深度为depth需要访问的节点数，这里计算的是在depth深度是满二叉树的情况下
- 空间复杂度：O(2depth-1)，表示在深度为depth需要创建的新的节点数为2depth-1个新TreeNode
