题目链接:https://leetcode.cn/problems/add-one-row-to-tree/
直接想法
这题的要求:根节点为深度1开始,在depth深度创建一个新的节点,把原来depth深度的节点,父节点的左子节点依旧为新节点的左子节点,右子节点依旧为新节点的右子节点。
这个时候我们可以用DFS从根节点开始遍历节点的左右节点,一直找到depth深度的节点,创建新的节点替换他,然后返回给父节点新的节点,对于depth深度存在问题,这里我们需要分类讨论
/**
* 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)
}