专业从事成都网站建设,怎么搭建网站 优帮云,网站开发网站,昆明做网站外包本题为修改给定二叉树中结点的值#xff0c;修改的规则为#xff1a;将原来的值替换为该结点所有堂兄弟结点值的和。
其实我们可以延申一下题意#xff0c;怎样去计算该结点所有堂兄弟结点值的和#xff1f;其实只需要先计算每一层所有结点的和#xff0c;再减掉其本身的… 本题为修改给定二叉树中结点的值修改的规则为将原来的值替换为该结点所有堂兄弟结点值的和。
其实我们可以延申一下题意怎样去计算该结点所有堂兄弟结点值的和其实只需要先计算每一层所有结点的和再减掉其本身的值和兄弟结点如有的值。 那么又怎样去计算每一层的结点值之和可以通过层序遍历来收集每一层中所有结点并计算求和。 在层序遍历中需要先创建一个队列并将结点添加至队列中接下来若队列不为空则遍历每一层即深度相同的节点并将对应的val相加得到和sum最后的结点值就是sum减去本结点值及其亲兄弟结点值啦
实现代码如下
class Solution {public TreeNode replaceValueInTree(TreeNode root) {//若当前遍历节点无堂兄弟节点则其值为0root.val0;QueueTreeNode queue new ArrayDeque();//根节点入队queue.add(root);while(!queue.isEmpty()) {int sum0;int sizequeue.size();//遍历每一层即深度相同的节点并将对应的val相加得sum//最后的结点值就是sum减去本结点值及其亲兄弟结点值for(TreeNode node:queue) {if(node.left!null) {sumnode.left.val;}if(node.right!null) {sumnode.right.val;}}//第二遍遍历将不算堂兄弟的val减去while(size--0) {TreeNode node queue.poll();//记录父节点的所有儿子结点val之和int sumofxy (node.left null ? 0 : node.left.val) (node.right null ? 0: node.right.val);//若该父节点node存在左右儿子则更改val后将儿子入队if(node.left!null) {node.left.valsum-sumofxy;queue.add(node.left);}if(node.right!null) {node.right.valsum-sumofxy;queue.add(node.right);}}}return root;}
}
