深度优先搜索、广度优先搜索 2 种算法，求解《623. 在二叉树中增加一行》
例题
623. 在二叉树中增加一行
给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。
注意，根节点 root 位于深度 1 。
加法规则如下:
给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。
cur 原来的左子树应该是新的左子树根的左子树。
cur 原来的右子树应该是新的右子树根的右子树。
如果 depth == 1 意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val 作为整个原始树的新根，而原始树就是新根的左子树。
示例 1:
输入: root = [4,2,6,3,1,5], val = 1, depth = 2
输出: [4,1,1,2,null,null,6,3,1,5]
答案
深度优先搜索
var addOneRow = function(root, val, depth) {
if (depth === 1) return new TreeNode(val, root)
if (depth === 2) {
root.left = new TreeNode(val, root.left)
root.right = new TreeNode(val, null, root.right)
} else {
if (root.left) root.left = addOneRow(root.left, val, depth - 1)
if (root.right) root.right = addOneRow(root.right, val, depth - 1)
}
return root
};function addOneRow(root: TreeNode | null, val: number, depth: number): TreeNode | null {
if (root === null) return null
if (depth === 1) return new TreeNode(val, root)
root.left = depth === 2 ? new TreeNode(val, root.left) : addOneRow(root.left, val, depth - 1)
root.right = depth === 2 ? new TreeNode(val, null, root.right) : addOneRow(root.right, val, depth - 1)
return root
};class Solution {
function addOneRow($root, $val, $depth) {
if ($depth === 1) return new TreeNode($val, $root);
if ($depth === 2) {
$root->left = new TreeNode($val, $root->left);
$root->right = new TreeNode($val, null, $root->right);
} else {
if ($root->left) $root->left = $this->addOneRow($root->left, $val, $depth - 1);
if ($root->right) $root->right = $this->addOneRow($root->right, $val, $depth - 1);
}
return $root;
}
}func addOneRow(root *TreeNode, val int, depth int) *TreeNode {
if root == nil {
return nil
}
if depth == 1 {
return &TreeNode{val, root, nil}
}
if depth == 2 {
root.Left = &TreeNode{val, root.Left, nil}
root.Right = &TreeNode{val, nil, root.Right}
} else {
root.Left = addOneRow(root.Left, val, depth - 1)
root.Right = addOneRow(root.Right, val, depth - 1)
}
return root
}class Solution {
public TreeNode addOneRow(TreeNode root, int val, int depth) {
if (depth == 1) return new TreeNode(val, root, null);
if (depth == 2) {
root.left = new TreeNode(val, root.left, null);
root.right = new TreeNode(val, null, root.right);
} else {
if (root.left != null) root.left = addOneRow(root.left, val, depth - 1);
if (root.right != null) root.right = addOneRow(root.right, val, depth - 1);
}
return root;
}
}public class Solution {
public TreeNode AddOneRow(TreeNode root, int val, int depth) {
if (depth == 1) return new TreeNode(val, root);
if (depth == 2) {
root.left = new TreeNode(val, root.left);
root.right = new TreeNode(val, null, root.right);
} else {
if (root.left != null) root.left = AddOneRow(root.left, val, depth - 1);
if (root.right != null) root.right = AddOneRow(root.right, val, depth - 1);
}
return root;
}
}struct TreeNode* newTreeNode(int val, struct TreeNode* left, struct TreeNode* right) {
struct TreeNode* n = malloc(sizeof(struct TreeNode));
n->val = val;
n->left = left;
n->right = right;
return n;
}
struct TreeNode* addOneRow(struct TreeNode* root, int val, int depth){
if (depth == 1) return newTreeNode(val, root, NULL);
if (depth == 2) {
root->left = newTreeNode(val, root->left, NULL);
root->right = newTreeNode(val, NULL, root->right);
} else {
if (root->left) root->left = addOneRow(root->left, val, depth - 1);
if (root->right) root->right = addOneRow(root->right, val, depth - 1);
}
return root;
}class Solution {
public:
TreeNode* addOneRow(TreeNode* root, int val, int depth) {
if (depth == 1) return new TreeNode(val, root, nullptr);
if (depth == 2) {
root->left = new TreeNode(val, root->left, nullptr);
root->right = new TreeNode(val, nullptr, root->right);
} else {
if (root->left) root->left = addOneRow(root->left, val, depth - 1);
if (root->right) root->right = addOneRow(root->right, val, depth - 1);
}
return root;
}
};class Solution:
def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
if root == None: return None
if depth == 1: return TreeNode(val, root)
root.left = TreeNode(val, root.left) if depth == 2 else self.addOneRow(root.left, val, depth - 1)
root.right = TreeNode(val, None, root.right) if depth == 2 else self.addOneRow(root.right, val, depth - 1)
return root广度优先搜索 · 层序遍历 · 记录深度
var addOneRow = function(root, val, depth) {
if (depth === 1) return new TreeNode(val, root)
const q = [root]
let head = 0, tail = 1, d = 0
while (head < tail) {
if (++d === depth) break
for (let l = tail - head; l--;) {
const n = q[head++]
if (n.left) q[tail++] = n.left
if (n.right) q[tail++] = n.right
if (d === depth - 1) {
n.left = new TreeNode(val, n.left)
n.right = new TreeNode(val, null, n.right)
}
}
}
return root
};function addOneRow(root: TreeNode | null, val: number, depth: number): TreeNode | null {
if (depth === 1) return new TreeNode(val, root)
const q = [root]
let head = 0, tail = 1, d = 0
while (head < tail) {
if (++d === depth) break
for (let l = tail - head; l--;) {
const n = q[head++]
if (n.left) q[tail++] = n.left
if (n.right) q[tail++] = n.right
if (d === depth - 1) {
n.left = new TreeNode(val, n.left)
n.right = new TreeNode(val, null, n.right)
}
}
}
return root
};class Solution {
function addOneRow($root, $val, $depth) {
if ($depth === 1) return new TreeNode($val, $root);
$q = [$root];
$head = 0;
$tail = 1;
$d = 0;
while ($head < $tail) {
if (++$d === $depth) break;
for ($l = $tail - $head; $l--;) {
$n = $q[$head++];
if ($n->left) $q[$tail++] = $n->left;
if ($n->right) $q[$tail++] = $n->right;
if ($d === $depth - 1) {
$n->left = new TreeNode($val, $n->left);
$n->right = new TreeNode($val, null, $n->right);
}
}
}
return $root;
}
}广度优先搜索 · 层序遍历 · 遍历到指定深度
func addOneRow(root *TreeNode, val int, depth int) *TreeNode {
if depth == 1 {
return &TreeNode{val, root, nil}
}
q, head := []*TreeNode{root}, 0
for i := 2; i < depth; i++ {
for tail := len(q); head < tail; head++ {
n := q[head]
if n.Left != nil {
q = append(q, n.Left)
}
if n.Right != nil {
q = append(q, n.Right)
}
}
}
for tail := len(q); head < tail; head++ {
q[head].Left = &TreeNode{val, q[head].Left, nil}
q[head].Right = &TreeNode{val, nil, q[head].Right}
}
return root
}class Solution {
public TreeNode addOneRow(TreeNode root, int val, int depth) {
if (depth == 1) return new TreeNode(val, root, null);
Deque<TreeNode> q = new ArrayDeque<TreeNode>();
q.offerLast(root);
while (depth-- > 2) {
for (int l = q.size(); l > 0; l--) {
TreeNode n = q.pollFirst();
if (n.left != null) q.offerLast(n.left);
if (n.right != null) q.offerLast(n.right);
}
}
while (q.isEmpty() == false) {
TreeNode n = q.pollFirst();
n.left = new TreeNode(val, n.left, null);
n.right = new TreeNode(val, null, n.right);
}
return root;
}
}public class Solution {
public TreeNode AddOneRow(TreeNode root, int val, int depth) {
if (depth == 1) return new TreeNode(val, root);
Queue<TreeNode> q = new Queue<TreeNode>();
q.Enqueue(root);
while (depth-- > 2) {
for (int l = q.Count; l > 0; l--) {
TreeNode n = q.Dequeue();
if (n.left != null) q.Enqueue(n.left);
if (n.right != null) q.Enqueue(n.right);
}
}
while (q.Count > 0) {
TreeNode n = q.Dequeue();
n.left = new TreeNode(val, n.left);
n.right = new TreeNode(val, null, n.right);
}
return root;
}
}struct TreeNode* newTreeNode(int val, struct TreeNode* left, struct TreeNode* right) {
struct TreeNode* n = malloc(sizeof(struct TreeNode));
n->val = val;
n->left = left;
n->right = right;
return n;
}
struct TreeNode* addOneRow(struct TreeNode* root, int val, int depth){
if (depth == 1) return newTreeNode(val, root, NULL);
struct TreeNode** q = malloc(sizeof(struct TreeNode*) * 1e4);
q[0] = root;
int head = 0, tail = 1;
while (depth-- > 2) {
for (int l = tail - head; l > 0; l--) {
struct TreeNode* n = q[head++];
if (n->left) q[tail++] = n->left;
if (n->right) q[tail++] = n->right;
}
}
while (head < tail) {
struct TreeNode* n = q[head++];
n->left = newTreeNode(val, n->left, NULL);
n->right = newTreeNode(val, NULL, n->right);
}
return root;
}class Solution {
public:
TreeNode* addOneRow(TreeNode* root, int val, int depth) {
if (depth == 1) return new TreeNode(val, root, nullptr);
queue<TreeNode*> q;
q.push(root);
while (depth-- > 2) {
for (int l = q.size(); l > 0; l--) {
TreeNode* n = q.front();
q.pop();
if (n->left) q.push(n->left);
if (n->right) q.push(n->right);
}
}
while (q.empty() == false) {
TreeNode* n = q.front();
q.pop();
n->left = new TreeNode(val, n->left, nullptr);
n->right = new TreeNode(val, nullptr, n->right);
}
return root;
}
};class Solution:
def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]:
if depth == 1: return TreeNode(val, root)
q = [root]
for _ in range(2, depth):
for _ in range(len(q), 0, -1):
n, q = q[0], q[1:]
if n.left: q.append(n.left)
if n.right: q.append(n.right)
for _, n in enumerate(q):
n.left, n.right = TreeNode(val, n.left), TreeNode(val, None, n.right)
return root