一
给你两棵二叉树: root1 和 root2 。
想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
分析
深度遍历和宽度遍历都可以,但是宽度遍历比较麻烦,他还需要另外开一个队列储存数值,在遍历二叉树的时候,我认为深度优先遍历是优于宽度优先遍历的
有两种思路,
1
直接将tree1合并到tree2中,当tree1有节点是空的情况下就直接将tree2的节点接在下面就好了。
遍历顺序是中根遍历,先遍历左节点,再是父节点,最后是右节点。
1 | if(root1!=nullptr&&root2!=nullptr)dfs(root1,root2); |
2
通过tree1和tree2新建立一个新树。每一层递归完成后面层数的树的构建,并将其返回给上一层,最后返回的就是一整颗树
1 | if(root1==nullptr)return root2;//tree1空,返回tree2 |
本文作者: jiangyuhao
本文链接: http://example.com/2022/03/29/%E6%B7%B1%E6%90%9C%E5%92%8C%E5%AE%BD%E6%90%9C2/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!