看了一篇文章说：
成功 = 核心算法(套路) + 大量重复动作。
我在想为什么这种递归题我做了也挺多的了还是不太6。
我现在觉得自己缺少套路。
weekly test 37的第二题。这题我调了两个小时。
我一直以为到了1的左子树之后，backtracking会再到1的右子树，而实际上它会跳过1那一层，直接回到1的上一层。所以我在用count==4这种希望它走到第四个count的时候（也就是第二个1的右孩子）的时候赋给右孩子，实际上直接回到首层就已经可以赋值了所以count = 2。
因为它会回到dfs()执行之前的那一层，而不是按照Tree的层级回去啊。其实往往是按照tree的层级回去的，但是由于我在d == 1的时候
public TreeNode addOneRow(TreeNode root, int v, int d) {
if (d == 1) {
TreeNode newNode = new TreeNode(v);
newNode.left = root;
return newNode;
}
dfs(root, 1, v, d);
return root;
}
TreeNode left;
TreeNode right;
int count = 0;
private void dfs(TreeNode root, int level, int v, int d) {
if (root == null) return;
if (level == d - 1) {
left = root.left;
right = root.right;
root.left = new TreeNode(v);
root.right = new TreeNode(v);
}
if (level == d) {
count++;
if (count == 1) {
root.left = left;
}
if (count == 2) {
root.right = right;
count = 0;
}
return;
}
dfs(root.left, level + 1, v, d);
dfs(root.right, level + 1, v, d);
}
然后我看了下答案，两分钟就写了一遍。。答案真是太直观了，根本不需要考虑回溯的问题。我是分两层dfs来拼接，第一层先拼，第二层再接，答案是直接在d-1的时候把拼接都做了，而且不用考虑count匹配的问题。下面是代码：
public TreeNode addOneRow(TreeNode t, int v, int d) {
if (d == 1) {
TreeNode root = new TreeNode(v);
root.left = t;
return root;
}
dfs(t, v, d, 1);
return t;
}
private void dfs(TreeNode t, int v, int d, int level) {
if (t == null) {
return;
}
if (level == d - 1) {
TreeNode node = t.left;
t.left = new TreeNode(v);
t.left.left = node;
node = t.right;
t.right = new TreeNode(v);
t.right.right = node;
return;
//return 等同于 else， 就是到这里就不需要继续往下拼接了
}
dfs(t.left, v, d, level + 1);
dfs(t.right, v, d, level + 1);
}
bfs解法：
感觉不需要两个queue的。
https://leetcode.com/articles/add-one-row-in-a-tree/#nodebb-comments
用bfs做了一遍：
写得很长，但是由于已经习惯了这种写法，一直也没有想去纠正；但是这种由于要手动控制curNum、nextNum，容易错，比如我就漏写了nextNum = 0 ;导致调试了很久。可以用while里面套for循环代替。
public TreeNode addOneRow(TreeNode root, int v, int d) {
if (d == 1) {
TreeNode newNode = new TreeNode(v);
newNode.left = root;
return newNode;
}
bfs(root, v, d);
return root;
}
private void bfs(TreeNode root, int v, int d) {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int curNum = 1;
int nextNum = 0;
int level = 1;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
curNum--;
if (level == d - 1) {
TreeNode temp = node.left;
node.left = new TreeNode(v);
node.left.left = temp;
temp = node.right;
node.right = new TreeNode(v);
node.right.right = temp;
}
if (node.left != null) {
queue.add(node.left);
nextNum++;
}
if (node.right != null) {
queue.add(node.right);
nextNum++;
}
if (curNum == 0) {
curNum = nextNum;
nextNum = 0 ;
level++;
}
if (level == d) {
break;
}
}
}
