C++怎么实现二叉树的堂兄弟节点查询

这篇文章主要介绍了C++怎么实现二叉树的堂兄弟节点查询的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇C++怎么实现二叉树的堂兄弟节点查询文章都会有所收获，下面我们一起来看看吧。

一.二叉树的堂兄弟节点

1.题目描述

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。

如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。

我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。

只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。

力扣:力扣

2.问题分析

题目中很详细的给出了判断堂兄弟节点的条件:①两个节点深度相同②父节点不同

由此我们可以通过BFS和DFS找到题目给定的两个值对应的二叉树结点,记录这两个结点的深度和父节点,最后通过判断堂兄弟结点的条件从而判断是否为堂兄弟结点.

3.代码实现

1.BFS解法

//x的信息intx;TreeNodexParent;intxDepth;booleanxFound=false;//y的信息inty;TreeNodeyParent;intyDepth;booleanyFound=false;publicbooleanisCousins(TreeNoderoot,intx,inty){this.x=x;this.y=y;LinkedList<TreeNode>queue=newLinkedList<>();intdepth=0;if(root!=null){queue.offer(root);if(root.val==x||root.val==y){returnfalse;}}while(!queue.isEmpty()){intsize=queue.size();for(inti=0;i<size;++i){TreeNodenode=queue.poll();if(node.left!=null){queue.offer(node.left);if(node.left.val==x){xParent=node;xDepth=depth;}if(node.left.val==y){yParent=node;yDepth=depth;}}if(node.right!=null){queue.offer(node.right);if(node.right.val==x){xParent=node;xDepth=depth;}if(node.right.val==y){yParent=node;yDepth=depth;}}}depth++;}returnxDepth==yDepth&&xParent!=yParent;}

2.DFS解法

//x的信息intx;TreeNodexParent;intxDepth;booleanxFound=false;//y的信息inty;TreeNodeyParent;intyDepth;booleanyFound=false;publicbooleanisCousins(TreeNoderoot,intx,inty){this.x=x;this.y=y;dfs(root,0,null);returnxDepth==yDepth&&xParent!=yParent;}publicvoiddfs(TreeNodenode,intdepth,TreeNodeparent){if(node==null){return;}if(node.val==x){xParent=parent;xDepth=depth;xFound=true;}elseif(node.val==y){yParent=parent;yDepth=depth;yFound=true;}//如果两个节点都找到了，就可以提前退出遍历//即使不提前退出，对最坏情况下的时间复杂度也不会有影响if(xFound&&yFound){return;}dfs(node.left,depth+1,node);if(xFound&&yFound){return;}dfs(node.right,depth+1,node);}

二.二叉树的堂兄弟节点 II

1.题目描述

给你一棵二叉树的根root，请你将每个节点的值替换成该节点的所有 堂兄弟节点值的和。

如果两个节点在树中有相同的深度且它们的父节点不同，那么它们互为 堂兄弟。

请你返回修改值之后，树的根root。

注意，一个节点的深度指的是从树根节点到这个节点经过的边数。

力扣:力扣

2.问题分析

每一次只需要求出下一层的所有节点的和,然后减去非子结点的值,就是其堂兄弟结点值的和了.

3.代码实现

publicTreeNodereplaceValueInTree(TreeNoderoot){root.val=0;ArrayList<TreeNode>queue=newArrayList<>();queue.add(root);while(!queue.isEmpty()){ArrayList<TreeNode>tmp=queue;queue=newArrayList<>();intnextLevelSum=0;//下一层的节点值之和for(TreeNodenode:tmp){if(node.left!=null){queue.add(node.left);nextLevelSum+=node.left.val;}if(node.right!=null){queue.add(node.right);nextLevelSum+=node.right.val;}}//再次遍历，更新下一层的节点值for(TreeNodenode:tmp){intchildrenSum=(node.left!=null?node.left.val:0)+(node.right!=null?node.right.val:0);if(node.left!=null)node.left.val=nextLevelSum-childrenSum;if(node.right!=null)node.right.val=nextLevelSum-childrenSum;}}returnroot;}

关于“C++怎么实现二叉树的堂兄弟节点查询”这篇文章的内容就介绍到这里，感谢各位的阅读！相信大家对“C++怎么实现二叉树的堂兄弟节点查询”知识都有一定的了解，大家如果还想学习更多知识，欢迎关注主机评测网行业资讯频道。

上一篇：java取得mac地址的代码怎么写

下一篇：Svelte和React的区别是什么

---