分享一个手撕

对树指定depth层，加入一层节点，节点数值为根结点到第depth层节点val值之和

然后这个新增节点指向原先节点的左右节点吗？感觉应该层序遍历，一个变量记录深度，一个 list 存当前层节点，一个存下一层节点，一个双端队列更新累计和吗，或者同样用两个 list？

这不层序遍历吗，很简单<br>【 在 IWhisper#305 的大作中提到: 】<br><font class="f006">: 然后这个新增节点指向原先节点的左右节点吗？感觉应该层序遍历，一个变量记录深度，一个 list 存当前层节点，一个存下一层节点，一个双端队列更新累计和吗，或者同样用两个 list？ </font>

我以为我理解错题目了<img src="/img/ubb/ema/2.gif" alt="ema2" style="display:inline;border-style:none">

没看明白，加入一层节点的意义何在，那不是和原树的depth层一下的节点没关系了

累计和怎么统计呢，当时卡到这里了，这个list怎么和前面的对上，因为不是满二叉树，后面想到其实可以在队列里面一边加的时候，把累计的和带上。<br>【 在 IWhisper#305 的大作中提到: 】<br><font class="f006">: 然后这个新增节点指向原先节点的左右节点吗？感觉应该层序遍历，一个变量记录深度，一个 list 存当前层节点，一个存下一层节点，一个双端队列更新累计和吗，或者同样用两个 list？ </font>

pair就好了吧<br>【 在 IWhisper#689 的大作中提到: 】<br><font class="f006">: 累计和怎么统计呢，当时卡到这里了，这个list怎么和前面的对上，因为不是满二叉树，后面想到其实可以在队列里面一边加的时候，把累计的和带上。 </font>

一个累计和就对应一个节点吧，没太理解什么意思，你是指如何判断相邻的两个是不是一个父节点的子节点吗，那加一个在层序便利中加一个标记位，int 的最大值或者最小值，但是节点和累计和不是一一对应吗，感觉我还是没理解题意，<img src="/img/ubb/ema/2.gif" alt="ema2" style="display:inline;border-style:none">，不过刚刚那个双端队列说错了，双端队列不行

你说的累计和是所有节点还是只那一条路径上的和？所有和不就单独用个int就行吗

我当时题也看了半天，一开始我还以为只给左右节点加，就是层续遍历，通过depth--去定位到对应的层，这时候队列中的就是要加的这一层。然后队列里面可以不光存节点，还可以存一个值，这个值是从父节点传下来的值，有一点像递归。从队列中把元素取出来。先把左右节点保存，创建新的左右节点，把val值放进去，旧的左树变成新的左结点的左结点，右树同理。<br>【 在 IWhisper#305 的大作中提到: 】<br><font class="f006">: 一个累计和就对应一个节点吧，没太理解什么意思，你是指如何判断相邻的两个是不是一个父节点的子节点吗，那加一个在层序便利中加一个标记位，int 的最大值或者最小值，但是节点和累计和不是一一对应吗，感觉我还是没理解题意，<img src="/img/ubb/ema/2.gif" alt="ema2" style="display:inline;border-style:none">，不过刚刚那个双端队列说错了，双端队列不行 </font>

不是递归，说错了，dp<br>【 在 IWhisper#689 的大作中提到: 】<br><font class="f006">: 我当时题也看了半天，一开始我还以为只给左右节点加，就是层续遍历，通过depth--去定位到对应的层，这时候队列中的就是要加的这一层。然后队列里面可以不光存节点，还可以存一个值，这个值是从父节点传下来的值，有一点像递归。从队列中把元素取出来。先把左右节点保存，创建新的左右节点，把val值放进去，旧的左树变成新的左结点的左结点，右树同理。 </font>

不是所有节点，是根结点到这个节点的和<br>【 在 IWhisper#688 的大作中提到: 】<br><font class="f006">: 你说的累计和是所有节点还是只那一条路径上的和？所有和不就单独用个int就行吗 </font>

感觉递归就行吧<br>func(node next, int sum, int depth, node pre)<br>【 在 IWhisper#689 的大作中提到: 】<br><font class="f006">: 不是所有节点，是根结点到这个节点的和 </font>

你说的有道理<br>【 在 IWhisper#688 的大作中提到: 】<br><font class="f006">: 感觉递归就行吧 </font><br><font class="f006">: func(node next, int sum, int depth, node pre) </font>

害，这样的题都没撕出来，看了半天题<img src="/img/ubb/em/7.gif" alt="em7" style="display:inline;border-style:none"><br>【 在 IWhisper#688 的大作中提到: 】<br><font class="f006">: 感觉递归就行吧 </font><br><font class="f006">: func(node next, int sum, int depth, node pre) </font>