leetcode-每日一题623. 在二叉树中增加一行(DFS)

题目链接：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(2^depth - 1)，表示遍历到深度为depth需要访问的节点数，这里计算的是在depth深度是满二叉树的情况下
• 空间复杂度：O(2^depth-1)，表示在深度为depth需要创建的新的节点数为2^depth-1个新TreeNode