BiruLyu
7/4/2017 - 7:33 PM

## 623. Add One Row to Tree(BFS).java

`````` public TreeNode addOneRow(TreeNode root, int v, int d) {
if (d < 2) {
TreeNode newroot = new TreeNode(v);
if (d == 0) newroot.right = root;
else newroot.left = root;
return newroot;
}
if (root == null) return null;
root.left = addOneRow(root.left, v, d == 2 ? 1 : d-1);
root.right = addOneRow(root.right, v, d == 2 ? 0 : d-1);
return root;
}``````
``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private void dfs(TreeNode root, int v, int level, int d) {
if (root == null) return;
if (level < d - 1) {
dfs(root.left, v, level + 1, d);
dfs(root.right, v, level + 1, d);
} else {
TreeNode t = root.left;
root.left = new TreeNode(v);
root.left.left = t;
t = root.right;
root.right = new TreeNode(v);
root.right.right = t;
}

}
public TreeNode addOneRow(TreeNode root, int v, int d) {
if (d == 1) {
TreeNode newRoot = new TreeNode(v);
newRoot.left = root;
return newRoot;
}
dfs(root, v, 1, d);
return root;
}
}``````
``````public TreeNode addOneRow(TreeNode root, int v, int d) {
if (d == 1) {
TreeNode newroot = new TreeNode(v);
newroot.left = root;
return newroot;
}
for (int i = 0; i < d-2; i++) {
int size = queue.size();
for (int j = 0; j < size; j++) {
TreeNode t = queue.poll();