AddOneRowToTree [source code]
public class AddOneRowToTree {
static
/******************************************************************************/
public class Solution {
public TreeNode addOneRow(TreeNode root, int v, int d) {
TreeNode res = new TreeNode(0);
if (d == 1) {
res.val = v;
res.left = root;
return res;
}
Queue<TreeNode> q = new LinkedList<>();
int depth = 0;
q.offer(root);
while (!q.isEmpty()) {
depth++;
int size = q.size();
if (depth + 1 == d) {
for (int i = 0; i < size; i++) {
TreeNode cur = q.poll();
TreeNode nodeL = new TreeNode(v), nodeR = new TreeNode(v);
nodeL.left = cur.left;
nodeR.right = cur.right;
cur.left = nodeL;
cur.right = nodeR;
}
return root;
} else {
for (int i = 0; i < size; i++) {
TreeNode cur = q.poll();
if (cur.left != null)
q.offer(cur.left);
if (cur.right != null)
q.offer(cur.right);
}
}
}
return root;
}
}
/******************************************************************************/
public static void main(String[] args) {
AddOneRowToTree.Solution tester = new AddOneRowToTree.Solution();
}
}
感觉好像不是很难的样子? 各种界定都很清晰. 如果用DFS/recursion做, 加一个depth的tag就行了; 但是好像这题用BFS好做一点?
需要注意的一点是这题要你完成的不是一个mutation, 而是最后返回值就是要有一个单独的tree;
另外一个小细节注意(你自己也应该想到, 因为关系到给的参数的范围: legitimate domain): d的取值范围是可以是最大depth+1的, 也就是可以在leaf level下面add; 这个情况好像在BFS里面不是特别的好处理; 先不管, 简单升级/relaxation, 先不考虑这个d的取值. //所以一开始不要用特殊情况或者优化来吓自己, 先写一个相对笨办法一点的代码, 写的过程当中就自然而然能够想到解决这些难题的办法; 比如这一题, 这个leaf level的取值的情况, 最后发现其实是根本不需要考虑的, 因为我们这里hit的判断其实判断的是当前level的下一个level; 所以如果你走到了leaf level, 然后判断成功, 正常的一样做就行了;
设置depth变量的时候, 要在自己的脑子里, based on iteration, 完成一个depth和level的对应: 对应某一个iteration(of a level), 你要能稍微trace一下, 确定这个level的depth是多少, 是不是你设计的值;
总体来说不是一个特别难的题目, 一遍就bug-free AC了; 最后的速度是11ms (32%), 不是特别理想, 不过好像BFS向来就没有recursion直接做来的快, 可能是因为recursion的优化比较好, 也有可能是因为BFS这个频繁的queue操作其实也不是free的;
editorial1的解法是DFS: > Inside every such call, we check if we've reached one level prior to the level where the new node needs to be inserted.
基本的一个思路跟我的做法还是比较类似的, 就是对depth的判断要提前一个level;
public class Solution {
public TreeNode addOneRow(TreeNode t, int v, int d) {
if (d == 1) {
TreeNode n = new TreeNode(v);
n.left = t;
return n;
}
insert(v, t, 1, d);
return t;
}
public void insert(int val, TreeNode node, int depth, int n) {
if (node == null)
return;
if (depth == n - 1) {
TreeNode t = node.left;
node.left = new TreeNode(val);
node.left.left = t;
t = node.right;
node.right = new TreeNode(val);
node.right.right = t;
} else {
insert(val, node.left, depth + 1, n);
insert(val, node.right, depth + 1, n);
}
}
}
注意这里的DFS的写法还是用的side effects的思路;
基本看来好像跟普通的BFS的差别也不是特别大, 无非就是加一个depth tag来帮助目标判断;
editorial2好像是强行把DFS翻译成iteration做的一个版本:
public class Solution {
class Node{
Node(TreeNode n,int d){
node=n;
depth=d;
}
TreeNode node;
int depth;
}
public TreeNode addOneRow(TreeNode t, int v, int d) {
if (d == 1) {
TreeNode n = new TreeNode(v);
n.left = t;
return n;
}
Stack<Node> stack=new Stack<>();
stack.push(new Node(t,1));
while(!stack.isEmpty())
{
Node n=stack.pop();
if(n.node==null)
continue;
if (n.depth == d - 1 ) {
TreeNode temp = n.node.left;
n.node.left = new TreeNode(v);
n.node.left.left = temp;
temp = n.node.right;
n.node.right = new TreeNode(v);
n.node.right.right = temp;
} else{
stack.push(new Node(n.node.left, n.depth + 1));
stack.push(new Node(n.node.right, n.depth + 1));
}
}
return t;
}
}
有空可以看一下. 注意他这里专门做了一个class来封装信息; 当然人家的初衷未必就是装逼, 可能是他首先更喜欢用DFS而不是BFS, 其次他希望不用recursion因为想要iteration的premature exit;
注意虽然是iteration, 还是用了depth tag的概念; 只不过现在没有参数列表的概念了, 所以就只能直接用一个class来实现封装; 但是最终得到的效果其实都是类似的;
我目前对于DFS的iteration写法还不是很熟悉, 所以也还不好说这里到底是什么order; 不过这个题目本身好像跟order也没有什么关系? 如果是用DFS做, 最终的实际内容就是对每一个node都进行一个匹配, 当depth匹配成功的时候就给一个side effect就行了;
脑子里举了一个简单的例子走了一下, 好像这个逻辑不是三种order当中的任何一种? 好像其实是node, 然后右, 然后左的一个做法. 但是还是像上面介绍的一样, 这个order在这里是无所谓的: 我们只要能够保证所有的tree node都被iterate到了就行, 以及depth tag维护的正确就行了(这个tag的维护无论你是什么order, 都是很好做的).
这个人的做法其实就是随便设计了一个用Stack做的DFS, 就为了iteration的premature exit的红利而已;
editorial3就是很直接的一个BFS做:
public class Solution {
public TreeNode addOneRow(TreeNode t, int v, int d) {
if (d == 1) {
TreeNode n = new TreeNode(v);
n.left = t;
return n;
}
Queue < TreeNode > queue = new LinkedList < > ();
queue.add(t);
int depth = 1;
while (depth < d - 1) {
Queue < TreeNode > temp = new LinkedList < > ();
while (!queue.isEmpty()) {
TreeNode node = queue.remove();
if (node.left != null) temp.add(node.left);
if (node.right != null) temp.add(node.right);
}
queue = temp;
depth++;
}
while (!queue.isEmpty()) {
TreeNode node = queue.remove();
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;
}
return t;
}
}
代码跟我有些微差别, 不过不算很大;
注意这里无论是我自己的答案还是他们的做法, 有一个共同的特点, 就是d等于1和大于1的情况都是分开处理的;
submission最优解:10(52):
public class Solution {
public TreeNode addOneRow(TreeNode root, int v, int d) {
if (d == 0 || d == 1) {
TreeNode newroot = new TreeNode(v);
newroot.left = d == 1 ? root : null;
newroot.right = d == 0 ? root : null;
return newroot;
}
if (root != null && d >= 2) {
root.left = addOneRow(root.left, v, d > 2 ? d - 1 : 1);
root.right = addOneRow(root.right, v, d > 2 ? d - 1 : 0);
}
return root;
}
}
翻了一下, 这个解法正好也是discussion最优解;
The idea is to:
In addition to use 1 to indicate attach to left node as required, we can also use 0 to indicate attach to right node;
这里首先一个小技巧, d直接减法而不是加法, 这个在涉及depth tag的其他问题里面, 前面也是碰到过的; 这一题的好处, 无非就是不用重新设计一个新的参数, 所以也可以帮助消除对helper的依赖;
这个是一个类似的改写的版本:
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;
}
这个版本比上面那个版本写的更好理解一些, 首先他这个用base case而不是noop来处理Null root的做法就更容易理解;
这个代码的核心是recursive call的这两行; 我们想看一个recursion算法的目的, 就是看在recursive call的时候参数表如何变化, 是一个非常重要的环节;
这个算法用到的trick, 其实就是给d这个参数赋予了非常丰富的内涵; 首先这里本身很简单的逻辑, 就是在d等于2的时候进行一个关键判断(比target提前一步). 如果是左边, 我们就正常-1, 但是如果是右边, 我们直接给你减到0. 这样左右两个分支就区分开来了, 直接在最后的一个level, 也就是target level对d参数进行判断, 就可以知道我们当前是left child还是right child;
Child Direction Judgment
这个需求其实一般见得不是很多, 但是有些题目还是有用的, 比如这一题, 明显就是有用的; 在target level的时候, 左右两个child的处理方式不一样(一个是加一个new left child, 一个是加一个new right child). 当有这个需求的时候, 常见的做法是参数表里面直接加一个flag(因为参数是recursive call获得信息的唯一途径(事实上, 全局变量也可以, 不过参数更简单)). 但是这里这个算法用到的思路更加简洁, 直接一个参数d多用;
这里有一个问题, 为什么可以分别用d等于1还是0来判断左右? 因为无论是0还是1, 都是base case了, 做完了就立刻返回了; 所以比如你是left base case, 解决完了之后你就没了, 不用给一个下一个d等于0的call了; 所以d等于1和0的两个base case是disjoint的, 这样来模拟一个flag是完全没有问题的;
那么为什么选择0 for right? 就是因为这个题目的一个Corner Case的设定; 就是d一开始等于1的情况, 我们需要的是加left child, 所以这里recursion的base case也用一样的对应的处理, 这样所有的处理都可以cover住;
这个算法也反映了我之前总结的一个漏洞:
Recursion也可以做到premature exit
如果你用side effect做的一个recursion, 那么确实无法做到premature exit, 这个是我之前对于这种做法没有意识到的一个缺点; 事实上, 只要你摆脱了这个死脑筋, recursion本身是可以做到premature exit的; 所谓的premature exit, 实际上就是要有一个valid return, 所以核心问题就是让你的recursion有一个实在的返回值就行; 就比如这里的;
另外tree问题里面, node直接作为返回值, 这个其实以前也是见过的, 比如之前学BST的时候的delete操作的时候, 就是这么做的; 如果一旦提到tree mutation, 脑子里只会side effect, 那未免还是太姜了;
另外一个帖子, 在一个trivial的DFS解法下面, 有人顺便讨论了一下, Null的判断, 到底是在leaf, 还是leaf之前的一层?
Almost the same as my solution, except the null check can be put before put a new layer into the stack, in this way, the stack can save a bout half. This is very useful when the tree is very big.
The position of the null checks that you have shown will not save half the stack. It would save 1 call stack entry per null node. At any given time there can be only 1 extra node inserted by my null checks. There will be a total of ~ 2*N extra nodes inserted if there are N' nodes with children = null over the course of the algorithm.
Nonetheless, your checks do save the additional time required to allocate a stack entry for an add call with a null node. Thanks for the insight, really made me think about my solution! :)
这个讨论还是挺有意思的;
除开这些, 这个题目的discussion基本就这样了, 没有太大的区别了;
Problem Description
Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1.
The adding rule is: given a positive integer depth d, for each NOT null tree nodes N in depth d-1, create two tree nodes with value v as N's left subtree root and right subtree root. And N's original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root's left subtree.
Example 1:
Input:
A binary tree as following:
4
/ \
2 6
/ \ /
3 1 5
v = 1
d = 2
Output:
4
/ \
1 1
/ \
2 6
/ \ /
3 1 5
Example 2:
Input:
A binary tree as following:
4
/
2
/ \
3 1
v = 1
d = 3
Output:
4
/
2
/ \
1 1
/ \
3 1
Note:
- The given d is in range [1, maximum depth of the given tree + 1].
- The given binary tree has at least one tree node.
Difficulty:Medium
Total Accepted:6.5K
Total Submissions:13.9K
Contributor: fallcreek
Companies
gilt groupe
Related Topics
tree